Suppose the following problem:

Given an undirected graph G=(V,E), is it possible to choose a subset V' of vertex set V, such that deleting it removes all triangles (cycles of length 3), where |V'| is at most k?

How can I construct a reduction from vertex cover problem into such problem?

  • $\begingroup$ Sorry, I missed the following info. You're supposed to choose V' such that it removes all triangles (cycle of length 3) $\endgroup$ – Ted Nov 12 '17 at 21:59

For every edge $(e_1, e_2)$ in the original VC instance, put edges $(e_1, e_2)$, $(e_1, e_{12})$ and $(e_{12}, e_2)$ in the graph of the instance of your problem.

There exists a vertex cover of size K in the original VC instance iff there exists a solution of size K in your problem. We see it:

=> : any vertex cover necessarily breaks all triangles already existing in the original graph of the VC instance, and also all newly created triangles in the new instance of your problem.

<= : given a set of nodes breaking all triangles in the new instance of your problem, for all nodes of the form $e_{ij}$ included in the set, replace it by $e_i$ or $e_j$. The resulting set of nodes will cover all edges in the original graph.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.