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).
$\begingroup$
$\endgroup$
4
asked Oct 5, 2020 at 9:48
-
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 ButterworthCommented Oct 5, 2020 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 ReddmannCommented Oct 5, 2020 at 15:01
-
2$\begingroup$ Here are some results which should be of interest: 1. The triangle removal lemma, which asserts that if a graph on $n$ vertices has $o(n^3)$ vertices, then those can be removed by deleting $o(n^2)$ edges. 2. By Turan's theorem, a triangle-free graph can have at most $\sim n^2/4$ edges. So starting with a complete graph, you need to remove at least $\sim n^2/4$ edges to remove all triangles. I'm not sure about the NP question, since I don't know what decision problem you have here. $\endgroup$– WojowuCommented Sep 15, 2021 at 22:40
-
$\begingroup$ Having put a bounty on this question, I would be primarily interested in bounds (for the number of edges needed to remove triangles) related closely in some sense to the number of edges, for example related to the maximum degree or the chromatic number or the Cheeger constant. $\endgroup$– Isky MathewsCommented Sep 16, 2021 at 0:35
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
Given a graph $G$, the problem of determining the minimum size $\tau(G)$ of a set of edges $X$ such that $G-X$ is triangle-free is indeed NP-complete. This was proved by Yannakakis. Regarding bounds for $\tau(G)$, we can consider the following dual problem. Let $\nu(G)$ be the maximum number of edge-disjoint triangles of $G$. Clearly $\nu(G) \leq \tau(G) \leq 3\nu(G)$. A famous conjecture of Tuza asserts:
$\tau(G) \leq 2\nu(G)$, for all graphs $G$.
The complete graph $K_4$ shows that this bound is best possible. Tuza's conjecture is still open, but it has been shown to hold for many restricted graph classes. For example it holds for threshold graphs by this recent paper of Bonamy, Bożyk, Grzesik, Hatzel, Masařík, Novotná, and Okrasa. The best general bound is by Haxell, who proved that $\tau(G) \leq \frac{66}{23} \nu(G)$ for all graphs $G$.
answered Sep 15, 2021 at 23:49
-
$\begingroup$ Given it's in NP (bummer!), this is probably the most extensive answer to get. THX. (Obviously, an additional "do only destroy one triangle per time" will make things even more complicated...or so I guess.) $\endgroup$ Commented Sep 16, 2021 at 18:33
-
$\begingroup$ @HaukeReddmann There may be no edges in a single triangle, so "only destroy one triangle at a time" might be impossible. $\endgroup$ Commented Jul 22 at 3:30