8
$\begingroup$

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.

$\endgroup$
12
$\begingroup$

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 (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 (Proceedings of symposium on Complexity of Computer Computations, 1972).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Many thanks! (When I googled this problem, I had no idea what to qualify "feedback edge set" with to find this.) $\endgroup$ – BPN Nov 1 '13 at 17:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.