NP-Completeness Solution

In an NP Reduction, we have a Problem B, and we want to show that it is NP-complete. These are the steps:

    • Demonstrate that problem B is in the class of NP problems. This is typically a description of a procedure that verifies a candidate solution. It needs to address the runtime.

    • Demonstrate that problem B is at least as hard as a problem believed to be NP-complete or NP-hard. This is done via reduction from a known problem A to the unknown problem B (A→ B) as follows:
        1. Show how an instance of A is converted to an instance of B in polynomial time.

        2. Show how a solution to the instance of B can be converted to a solution for the initial instance of A, again in polynomial time.

        3. Furthermore, you must show that a solution for B exists if-and-only-if (IFF) a solution to A exists. This means that, after proving the previous step, you are left with checking that if there is no solution for B, then no solution exists for A. This may be done via the contra-positive approach, showing that if a solution exists for A then a solution for B must exist.

The second bullet point above is the proof that problem B is NP-hard which combined with the first bullet point yields the NP-complete proof.

You are allow to declare the following problems in the class NP-hard without further justification.

    • SAT, 3-SAT, IS, Vertex Cover, Rudrata (or Hamiltonian) Cycle, Rudrata (or Hamiltonian) Path.

1.) (10 points each) Show that each of the following problems is in NP. This corresponds to completing the first bullet point of the outline on the first page. For each one, assume thatS is a potential solution to the problem; you must show how you can verify that S is indeed a solution in polynomial time.

(a.) Given an array of n distinct integers, return those integers sorted in ascending order.


:



(b.) Given a directed acyclic graph, G = (V, E) of n vertices, return a valid topological sorting of that graph.


Solution:
(c.) Given a family of sets {S1, S2, ..., Sn} and a budget b, return a set H of size ≤ b which intersects every Si.


Solution:

2.) (7.5 points each) We will prove that the following problem is NP-complete. Define the Length-K Rudrata Path (we will call this LKP for short) problem as: given an undirected graph G = (V, E) of n vertices and integer an k, is there a path in G that passes through exactly k vertices? Note that Rudrata and Hamiltonian mean the same thing.

(a.) We first show that a solution to this problem can be verified in polynomial time. LetS be a sequence of vertices. Provide a polynomial time algorithm to check that this is a valid solution to the LKP problem.


Solution:



(b.) Show how to take an input I to the Rudrata Path problem and convert it to an input I′ of LKP. Recall that LKP takes as input a graph G and an integer k, whereas Rudrata Path only takes as input a graph G.




(c.) Show how S′ , a solution of LKP on input I′ , can be turned into S, a solution of Rudrata Path on input I.


Solution:



(d.) Show that there exists a solution S′  to LKP on input I′  if-and-only-if there exists a solution
    • to Rudrata Path on input I.


Solution:

3.) (35 points) The Almost-SAT problem takes as input a boolean formula on n literals, in conjunctive normal form with m clauses. The output is an assignment of the literals such that exactly m−1 clauses evaluate to TRUE, if such assignment exists, and the output is NO, otherwise. Show that Almost-SAT is NP-complete.



Solution:





4.) (5 points) Hooray! You made it to your last homework problem for CS 3510. Name your favorite algorithm you learned this semester. 


Solution: