Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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.
