CODEWITHSUNDEEP
algorithmgraphgraph-theorynp-complete
Garrett
Garrett

Reputation: 11725

Reducing from Vertex Cover to prove NP-complete

We define ROMAN-SUBSET as the following problem:

INPUT: Directed graph G = ( V , E ) and a positive integer k

OUTPUT: If there is a subset R of V such that | R | <= k , and such that every directed circuit in G includes at least one vertex from R , then the output should be "TRUE", otherwise, it should be "FALSE".

Assuming that the Vertex Cover (VC) problem is NP-complete, I must prove that ROMAN-SUBSET is also NP-complete. From what I understand, that means taking the VC input, modifying it, and then showing that plugging it into the ROMAN-SUBSET algorithm will yield the result of the VC problem.

I'm having a really tough time coming up with the transformation. I know that the VC input is a graph G and an integer k, and the problem is whether or not there exists a subset R of V that covers every edge in G, such that |R| <= k. So clearly, the R and k are similar from ROM to VC, but my difficulty is identifying how to transform the graph so that 1 vertex in every directed cycle (for ROM) corresponds to every edge (for VC). How can I go about modifying the graph to prove that VC can be reduced to ROM?

Thanks!

Upvotes: 2

Views: 5216

Answers (1)

Petar Ivanov
Petar Ivanov

Reputation: 93050

Here is the construction.

Take undirected graph G = (V, E) as in VC. Now define the directed graph G1 = (V, E1), where for every edge (u,v) in E there are two edges (u,v) and (v,u) in E1.

In other words the new graph is the same as the old one, but every undirected edge is replaced with two directed edges that form a 2-cycle.

The claim is that from ROM on G1 follows VC on G.

Indeed, suppose that the answer for ROM on G1 is FALSE. Then for every choice of a set of less than k vertices there exists a cycle not in this set. So there exists an edge whose endpoints are not in the set. But this means that for the same choice of the set of less than k vertices in G there exists an edge whose endpoints are not in the set, so VC's answer is FALSE.

Conversely, suppose that the answer for ROM on G1 is TRUE. Then there exists a subset of V containing less than k vertices, so that given any cycle there exists at least one vertex in the cycle, which is in the set. But this means that for any edge in E one of its endpoints in in the set, because an edge in E corresponds to a 2-cycle in E1. Thus the answer for VC is TRUE.

Upvotes: 3

Related Questions