Show that the following problems are in NP. 1. MEDIAN = {<A, m> | A is an array

Question

Show that the following problems are in NP.

1. MEDIAN = {<A, m> | A is an array of 2n + 1 numbers and m is its median}.

2. HALF-CLIQUE = {<G> | G is an undirected graph having a clique of n 2 elements where the graph G has n elements }.

3. DOUBLE-SAT = {<> | has at least two satisfying assignments}.

4. DOMINATING-SET = {<G, k> | G has a dominating set with k nodes}. A dominating set of a graph G is the set of nodes N such that vertices v G, y N such that either v = y or v and y are adjacent.

Explanation / Answer

Ans:

2. Ans: If we perform a reduction of CLIQUE to HALF-CLIQUE showing that if we could solve

              HALF-CLIQUE in polynomial time we could solve CLIQUE as well. Let < G, k > be an

              instance of CLIQUE. If k |G|/ 2 then add j = 2k |G| vertices to G without adding any

              edges and run HALF-CLIQUE on this altered graph, G” . If G” has a half clique then it

             must be a clique of size k in the original graph G. If k < |G|/ 2 then add m = |G| 2k

             vertices and completely connect them to G and each other. Now, G” has 2|G| 2k

            vertices. If G” has a half-clique it is of size |G| k. Only m of these nodes could have

            been added so G must have a clique of size |G| k m = |G| k |G| + 2k = k.

            So, HALF-CLIQUE IS NP-COMPLETE.

3. Ans: To show that DOUBLE-SAT problem is NP-complete, we can reduce 3SAT to DOUBLE-SAT.

               Reduction of 3SAT to DOUBLE-SAT:

Given an input 3CNF , we create a new clause C = u u¯, where u is a newly added variable. Let ‘ = f() = C. So the function f(·) can be computed in polynomial time. We claim that 3SAT ‘ DOUBLE-SAT.

If 3SAT, assume a satisfying assignment is x = s where x is the variable vector of . Then we have at least two satisfying assignments for ‘ , because x = s, u = 1 and x = s, u = 0 are both satisfying assignments for ’

If ’ DOUBLE-SAT, then we know that must also be satisfiable because C is satisfiable. So 3SAT. This shows that DOUBLE-SAT is NP-hard.

It is also in NP. The certificate is two satisfying assignments. The verifier is a TM, M running in polynomial time, which tests whether the input 3CNF is satisfied by both the two assignments and the two assignments are different. This shows DOUBLE-SAT is in NP.

So it is in NP-complete.

4. Ans: To show DOMINATING-SET in NP, we reduce VERTEX COVER to DOMINATING-SET.

For every string x, we will prove that another string x’ can be constructed in polynomial time such that x VERTEX COVER x’ DOMINATING-SET. Let x = <G, k> where G = (V, E). we can construct x’ in the following way. First we construct another graph G’ = (V’ , E’ ) using G. Without lost of generality, assume that G does not have vertices which has degree 0.

Let V’ = V VE where VE is a set of new vertices such that each vertex ve VE if and only if e E. On the other hand, let E’ = E E˜. Here E˜ includes the edges (ve, u) and (ve, w) for every ve VE where we denote e = (u, w). Let x’ = (G’ , k).

Next we are showing that x VERTEX COVER x’ DOMINATING-SET. If G has a vertex cover C of size k, then G’ has a dominating set of size k. To see this, we claim the dominating set of G’ is exactly C. Let’s consider every vertex in G’ . For every v V , as we have assumed that v has degree at least 1, it is connected with an edge of E. As C is a vertex cover, this edge is connected with a vertex of C. So either v is in C or v is adjacent to a vertex in C. For every ve VE, as the edge e E is connected with a vertex in C, according to our definition of ve, we know that ve is also adjacent to that vertex. As a result, C is a dominating set of G’ . On the other hand, if G’ has a dominating set which is D of size k, we claim that a vertex cover C for G of size k can be found. Next we describe an algorithm to find C. First let C be the empty set. Then for each vertex v in D, if v V , put v into C. If v VE, assuming it corresponds to the edge e = (u, w), put either u or w into C. As a result, |C| k. Consider every edge e = (u, w) E. We know ve is adjacent to a vertex v’ of D. This vertex can only be ve, u or w. In any case, one of u and w is in C which covers the edge e. As a result, C covers all the edges. This means it is a vertex cover of size at most k for G.

So DOMINATING-SET is NP-hard.

Now we will show that it is in NP

For x = <G = (V, E), k> the certificate is a set D of vertices such that D V . Thus |D| |V |. The verifier TM M checks whether D is a dominating-set of size k for G. This checking can be accomplished in polynomial time as we can check the vertices one by one to make sure that each vertex is either in D or adjacent to a vertex in D. According to the definition of NP, DOMINATING-SET is in NP.

As a result, DOMINATING-SET is NP-complete.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.