<p>The undirected version is NP-hard. More specifically, the following problem, known as <strong>Partial Feedback Edge Set</strong> is NP-complete: given an undirected graph&nbsp;$G$, and positive integers $K$ and $L$, is there a set of at most $K$&nbsp;edges that contains at least one edge from every cycle of length at most&nbsp;$L$ in&nbsp;$G$.  This is still NP-complete for any fixed $L\geq 3$, and if $G$&nbsp;is restricted to be bipartite (in which case, $L$&nbsp;may also be fixed to any value of at least&nbsp;$4$).</p>

<p>For the directed case, Karp's proof that Feedback Arc Set is NP-complete  actually shows that it's NP-complete to determine if you can remove all directed $4$-cycles from an oriented graph by deleting at most $k$&nbsp;edges. (His reduction from Vertex Cover produces an oriented, triangle-free graph in which deleting all $4$-cycles deletes all cycles.) But that's not what you're asking.</p>

<p>Sources: The undirected version is problem GT9 of Garey and Johnson, <em>Computers and Intractability</em> (Freeman, New York, 1979). The original paper was Yannakakis, <em><a href="http://dl.acm.org/citation.cfm?doid=800133.804355" rel="nofollow">Node- and edge-deletion NP-complete problems</a></em> (Proceedings of STOC 1978) but it doesn't seem to contain a proof. Karp's Feedback Arc Set proof is on page&nbsp; of the "21&nbsp;problems" paper: <em><a href="http://cgi.di.uoa.gr/~sgk/teaching/grad/handouts/karp.pdf" rel="nofollow">Reducibility among combinatorial problems</a></em> (Proceedings of symposium on Complexity of Computer Computations, 1972).</p>

CC BY-SA 3.0
2013-11-01T17:05:40.530Z
Many thanks! (When I googled this problem, I had no idea what to qualify "feedback edge set" with to find this.)
BPN
CC BY-SA 3.0
2013-11-01T17:02:40.643Z
2013-11-04T19:04:19.423Z
2013-11-04T19:04:19.423Z
David Richerby
<p>Given a graph $G$, what is the minimum number of edges of $G$ that we need to delete to make the graph triangle free? To my untrained eye, this appears to be a difficult problem. </p>

<p>Is this problem known to be NP-complete? What about the analogue for oriented graphs (i.e., digraphs with no parallel edges) and directed 3-cycles? References would be greatly appreciated!</p>

<p>EDIT: David has very helpfully answered my question, in the undirected case, below. Any information on the directed/oriented version would be much appreciated.</p>

<cc.complexity-theory><graph-algorithms><np-hardness>
Minimum Triangle Covers
BPN
# Minimum Triangle Covers

(Asked by: username_0 on 2013-11-01)

Given a graph $G$, what is the minimum number of edges of $G$ that we need to delete to make the graph triangle free? To my untrained eye, this appears to be a difficult problem.

Is this problem known to be NP-complete? What about the analogue for oriented graphs (i.e., digraphs with no parallel edges) and directed 3-cycles? References would be greatly appreciated!

EDIT: David has very helpfully answered my question, in the undirected case, below. Any information on the directed/oriented version would be much appreciated.

**Tags:** cc.complexity-theory, graph-algorithms, np-hardness


---

## 1 answers

### Answer by username_1 on 2013-11-01. Score: 12

The undirected version is NP-hard. More specifically, the following problem, known as **Partial Feedback Edge Set** is NP-complete: given an undirected graph $G$, and positive integers $K$ and $L$, is there a set of at most $K$ edges that contains at least one edge from every cycle of length at most $L$ in $G$. This is still NP-complete for any fixed $L\geq 3$, and if $G$ is restricted to be bipartite (in which case, $L$ may also be fixed to any value of at least $4$).

For the directed case, Karp's proof that Feedback Arc Set is NP-complete actually shows that it's NP-complete to determine if you can remove all directed $4$-cycles from an oriented graph by deleting at most $k$ edges. (His reduction from Vertex Cover produces an oriented, triangle-free graph in which deleting all $4$-cycles deletes all cycles.) But that's not what you're asking.

Sources: The undirected version is problem GT9 of Garey and Johnson, *Computers and Intractability* (Freeman, New York, 1979). The original paper was Yannakakis, *[Node- and edge-deletion NP-complete problems](http://dl.acm.org/citation.cfm?doid=800133.804355)* (Proceedings of STOC 1978) but it doesn't seem to contain a proof. Karp's Feedback Arc Set proof is on page  of the "21 problems" paper: *[Reducibility among combinatorial problems](http://cgi.di.uoa.gr/~sgk/teaching/grad/handouts/karp.pdf)* (Proceedings of symposium on Complexity of Computer Computations, 1972).

> **Comments:**
> **username_0**: Many thanks! (When I googled this problem, I had no idea what to qualify "feedback edge set" with to find this.)  

---

