<p>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.</p>

<p>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:</p>

<p>=> : 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.</p>

<p>&lt;= : 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.</p>

CC BY-SA 3.0
2017-11-18T00:40:55.450Z
2017-11-18T00:40:55.450Z
EXPTIME-complete
<p>Suppose the following problem:</p>

<p>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? </p>

<p>How can I construct a reduction from vertex cover problem into such problem? </p>

CC BY-SA 3.0
2017-11-12T21:59:53.280Z
Sorry, I missed the following info. You're supposed to choose V' such that it removes all triangles (cycle of length 3)
Ted
<np-hardness><complexity-classes>
Proving NP-complete problem
Ted
# Proving NP-complete problem

(Asked by: username_0 on 2017-11-12)

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?

**Tags:** np-hardness, complexity-classes

> **Comments:**
> **username_0**: Sorry, I missed the following info. You're supposed to choose V' such that it removes all triangles (cycle of length 3)  

---

## 1 answers

### Answer by username_1 on 2017-11-18. Score: 0

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.


---

