Consider the following two decision problems: Problem A: Given an undirected gra
ID: 3861169 • Letter: C
Question
Consider the following two decision problems:
Problem A: Given an undirected graph G = (V, E), does there exist a non-empty subset S of V such that each edge in E is incident upon (i.e., includes) some vertex in S?
Problem B: Given a directed graph G = (V, E), does there exist a non-empty subset S of V such that every cycle in G contains a vertex in S?
a. Prove (i.e., provide a solid explanation as to why) Problem A is an NP problem.
b. Assume that Problem B is NP-complete. Show that Problem B reduces to Problem A.
Note: Class NP (Nondeterministic Polynomial): Problems for which nondeterministically finding a solution takes polynomial time which is not realistic!
Explanation / Answer
There is given an undirected graph G = (V, E), a vertex cover is S V such that if (p, q) is an edge of G, where either p S or q S .
VERTEX-COVER, is required to determine if a graph has a vertex cover of set of nodes having size k. As VERTEX-COVER is NP-Complete, by reducing method then a clique, is generated as the subset of vertices which are directly connected.
In case of an undirected graph G = (V, E), if a clique is S V of vertices , then each pair of S is connected by an edge in E, here again CLIQUE, is required to define if it has nodes of size k or not in a graph. Now proving that CLIQUE is NP Complete, we should implement from VERTEX-COVER by reduction .
Here, proving that CLIQUE NP , considering all problems is computable in NP have to be verifiable in polynomial time.
Then, in this part by check the solution to CLIQUE is computable in polynomial time or not, we have to follow some computational intractability.
-- let us consider , that the provided graph G = (V, E) and an independent set of vertices an integer as k, having a solution S V .
Now, checking if |S | = k ,then for every pair of vertices( u, v) S , and also if the edge (u, v) is in E.
The first check can be computed in |S | steps and the second check in |S | 2 steps , verification time complexity is O(n2 ) time, and CLIQUE NP.
Now if deducing that VERTEX-COVER will be reduced to CLIQUE.
As it is already proved that VERTEX-COVER is NP Complete if it reduced to CLIQUE, which is NP Complete.
An undirected graph G = (V, E),
The complement of G as G’ = (V, E’), here, E’ = {(u, v) : u, v V, u v,(u, v) E}.
G’ must have the same set of vertices as G, here we consider that if S in G, then V S has a vertex cover in G.
The algorithm from VERTEX-COVER(G, k) is reduced to :
1. A graph G = (V, E) and k>1
2. The complement graph G’ = (V, E’)
3. Reduce to CLIQUE(G’, |V | k)
4. If there is a solution then True else False
• there has to be a VERTEX-COVER(G, k) if it must be solvable to CLIQUE(G’, |V | k) and vise versa.
Lets consider, that G has a vertex cover S V , having |S | = k. So the vertex cover must considerall edges.
That for all u, v V , if u S and v S , then (u, v) E and thus (u, v) E’.
For any vertex pair both are not in the vertex cover S of G, an edge in G’.
So, also V S is a clique in G’, V S has size |V | k.
Here the complement graph, need a copy over all pairs of vertices of the original graph, which can be done in polynomial time. Therefore VERTEX-COVER can be reduced to CLIQUE is solvable in polynomial time, as CLIQUE NP where both VERTEX-COVER and CLIQUE are NP-Complete.