I'm sure it is well-known how many edges you must delete in a (highly linked) graph to destroy all cycles. Is it also known how many edges you must delete to destroy only all triangles? And even, how many you need if additionally, you may not use an edge to destroy more than one triangle? (Note the latter doesn't mean you can't touch a common edge, but after deleting this edge only one triangle "counts" as destroyed. Thus you need 4 edges for the graph $K_4$, and $K_6$ has no solution.)
A reference would be welcome, especially if the problem would be in NP (but a non-NP lower bound around $O(n^2)$ would also be fine).

  • 1
    $\begingroup$ Is this equivalent to: 1) find the set of all triangles; 2) find a set of edges, exactly one from each triangle? $\endgroup$ – Ray Butterworth Oct 5 at 13:40
  • $\begingroup$ Yes, there should be a bijection (for the variant question). (The graphs I deal with don't have O(n^2) size, but rather O(n*log(n)) - the question is a spinoff of binary search - , so I expect such a bijection to exist.) $\endgroup$ – Hauke Reddmann Oct 5 at 15:01

Your Answer

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

Browse other questions tagged or ask your own question.