NPC: Reduction of VC to 2VC

Question

A professor gave us this problem, which I could not solve: Reduce VC to 2VC. (Prove that 2VC is NPC)

Definition: 2VC gets G, and K, and returns true if there are 2 different VC in size K in G. (In the same way that double clique finds 2 clicks in size K)

Note: The problem was not written in English, so my translation might be slightly mistaken.

How should I go about solving it?

So far, I tried duplicating the graph, in the same way double-clique is reduced, but it doesn't help.

VC - known problem called Vertex Cover. https://en.wikipedia.org/wiki/Vertex_cover, 2VC is defined above. — Amit, Mar 07 '17 at 15:21

score 1 · Accepted Answer · answered Mar 07 '17 at 15:26

1

Add two new vertices joined by an edge, and adjust $k$ appropriately.

answered Mar 07 '17 at 15:26

hmakholm left over Monica

286,031

why did you edit out "k+1"? what case doesn't hold with k+1? – Amit Mar 07 '17 at 15:28
@Amit: I decided to give a slightly less complete solution, is all. – hmakholm left over Monica Mar 07 '17 at 15:29
Thanks, this solution is so simple and elegant. – Amit Mar 07 '17 at 15:30

NPC: Reduction of VC to 2VC

1 Answers1