# NP-completeness of triangle removal problem

Triangle removal problem states that, given an undirected graph G, can you pick a subset S of vertices such that removing S will remove all triangles from the old graph and |S| <= k. I was trying to use reduce from vertex cover problem, but every construction I attempted has failed. Here's what I've done:

1) Add extra edges to the graph such that every pair of distinct vertices is connected by an edge (In other words, create a complete graph Kn)

2) Create a subgraph of G, but only composed of vertices with degree at least 2 from the original graph

I found a counter example for each construction, and I can't fully grasp the starting point. The goal is that I want to build some graph out of an old graph such that the every triangle should use at least one vertex in S(solution returned by black box for "triangle removal problem"), but it has to be a vertex cover for the old graph at the same time. How should I approach this?

Edit: Current attempt - for every existing edge (u,v) in E in a graph, add a new vertex w and add two new edges (u,w) and (w,v) so that it forms a triangle

Your current attempt (at the time of writing this answer at least) is on the right track, it just needs one more step.

To help understand one way of relating the problems to each other, consider the following alternative way of defining a vertex cover; a vertex cover is a set of vertices whose removal leaves a disconnected graph.

So Vertex Cover is the problem of selecting vertices to remove that gets rid of all edges, whereas your problem is selecting vertices to get rid of triangles.

Thus to convert Vertex Cover to Triangle Removal we need to turn edges in the original graph intro triangles in the new graph (or at least, one sensible way - there could be many reductions).

Hence your construction of adding a vertex for every edge in the graph and making a triangle is heading in the right direction, the only problem is that we could remove the new vertices, and that may mess up our answer (it certainly makes it harder to argue about what the vertex cover should be in the original graph). What we need is a way of preventing the added vertices being selected for removal. To do this, instead of adding a single new vertex, add $k+1$ new vertices!

More precisely (but not completely precisely), given $G$ we construct $G'$ as follows:

• For every vertex $v \in V(G)$, there is a vertex $v' \in V(G')$
• For every edge $uv \in E(G)$, there is an edge $u'v' \in E(G')$.
• For every edge $uv \in E(G)$, there are $k+1$ vertices $\{w_{1},\ldots,w_{k+1}\} \subseteq V(G')$ with the edges $u'w_{i}$ and $v'w_{i}$ in $E(G')$ for all $i$.

I won't go through the full proof that this works, but the general gist is that if we want to get rid of all the triangles attached to $u'v'$, it doesn't really help to take any of the $w_{i}$ vertices as there are too many of them, we eventually have to take at least one of $u'$ or $v'$, but once we take one of those, it deals with all the triangles, so any answer that takes a $w_{i}$ vertex must also take $u'$ or $v'$ (or both) and can be replaced by a smaller solution that takes only $u'$ or $v'$ (or both), so we only have to consider solutions of that form, but then we're basically done - as each edge has triangles, one of the two "original" vertices must be in the triangle removing solution for each edge, and hence is also a vertex cover.

Really you can make the same argument with your construction, but the additional vertices force things and make the argument clearer (you don't have to deal with arguing for alternative solutions and vertex swapping etc. etc.)

• Thanks for the brilliant explanation. Especially for the first part how you think about reduction process helped me a lot – Ted Nov 13 '17 at 3:10