# Minimum Triangle Covers

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.

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.