The Longest Path Problem (LPP) is: "Given a directed graph G and a positive integer k, does there exist a simple path of vertex length at least k in G?" What is the answer for the LPP on a complete graph with n vertices and parameter k=n ? Yes 2n(n+1) Impossible to verify No The Max-3CNF problem is: "Given a 3-CNF formula with c clauses and a positive integer k, does there exist an assignment to the variables that satisfies at least k clauses?' If we wanted to show that this problem is NP-complete, how would we show that 3CNFMax3CNF? Given a 3CNF instance, transform it to a Max3CNF instance by letting k=c. This problem is not NP-complete. Given a 3CNF instance, transform it to a Max3CNF instance by letting k=c. Given a 3CNF instance, transform it to a Max3CNF instance by letting k=c2. When performing a depth-first search, assume that vertex A is finished before vertex B. Which of the following statements must be true? Both of the statements are required to be true. * Vertex B is discovered before vertex A. Vertex A is discovered before vertex B. Neither of the statements is required to be true. What can we say about a minimum cut of a network that separates a source from a sink when we perform the maximum flow? There exists a minimum cut with all edges saturated. No edge in the minimum cut can have flow through it. Nothing can be concluded. There exists a network such that, in every minimum cut of the network, there exists an edge that is not saturated