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

