Sufficient Conditions for Tuza’s Conjecture on Packing and Covering Triangles

Abstract

Given a simple graph $G=(V,E)$, a subset of E is called a triangle cover if it intersects each triangle of G. Let $\nu _t(G)$ and $\tau _t(G)$ denote the maximum number of pairwise edge-disjoint triangles in G and the minimum cardinality of a triangle cover of G, respectively. Tuza conjectured in 1981 that $\tau _t(G)/\nu _t(G)\le 2$ holds for every graph G. In this paper, using a hypergraph approach, we design polynomial-time combinatorial algorithms for finding small triangle covers. These algorithms imply new sufficient conditions for Tuza’s conjecture on covering and packing triangles. More precisely, suppose that the set $\mathscr {T}_G$ of triangles covers all edges in G. We show that a triangle cover of G with cardinality at most $2\nu _t(G)$ can be found in polynomial time if one of the following conditions is satisfied: (i) $\nu _t(G)/|\mathscr {T}_G|\ge \frac{1}{3}$, (ii) $\nu _t(G)/|E|\ge \frac{1}{4}$, (iii) $|E|/|\mathscr {T}_G|\ge 2$.

Research supported in part by NNSF of China under Grant No. 11531014 and 11222109.

1 Introduction

Graphs considered in this paper are undirected, simple and finite (unless otherwise noted). Given a graph $G=(V,E)$ with vertex set $V(G)=V$ and edge set $E(G)=E$, for convenience, we often identify a triangle in G with its edge set. A subset of E is called a triangle cover if it intersects each triangle of G. Let $\tau _t(G)$ denote the minimum cardinality of a triangle cover of G, referred to as the triangle covering number of G. A set of pairwise edge-disjoint triangles in G is called a triangle packing of G. Let $\nu _t(G)$ denote the maximum cardinality of a triangle packing of G, referred to as the triangle packing number of G. It is clear that $1\le \tau _t(G)/\nu _t(G)\le 3$ holds for every graph G. Our research is motivated by the following conjecture raised by Tuza [11] in 1981.

Conjecture 1

(Tuza’s Conjecture [11]). $\tau _t(G)/\nu _t(G)\le 2$ holds for every graph G.

The conjecture is still unsolved in general. If it is true, then the upper bound 2 is sharp as shown by $K_4$ and $K_5$ – the complete graphs of orders 4 and 5. Throughout, by extremal graphs we mean graphs G with $\tau _t(G)/\nu _t(G)=2$.

Related Work. The only known universal upper bound smaller than 3 was given by Haxell [7], who showed that $\tau _t(G)/\nu _t(G)\le 66/{23} =2.8695...$ for all graphs G. Haxell’s proof [7] implies a polynomial-time algorithm for finding a triangle cover of cardinality at most 66/23 times that of some maximal triangle packing.

Other partial results on Conjecture 1 concern special classes of graphs. Tuza [12] confirmed the conjecture for planar graphs, $K_{5}$-free chordal graphs and graphs with n vertices and at least $7n^{2}/16$ edges. The proof for planar graphs [12] gives an elegant polynomial-time algorithm for finding a triangle cover in planar graphs with cardinality at most twice that of some maximal triangle packing. The validity of Conjecture 1 on the class of planar graphs was later generalized by Krivelevich [9] to the class of graphs without $K_{3,3}$-subdivision. Haxell and Kohayakawa [8] showed that $\tau _t(G)/\nu _t(G)\le 2-\epsilon$ for tripartite graphs G, where $\epsilon > 0.044$. Haxell et al. [6] proved that every $K_{4}$-free planar graph G satisfies $\tau _t(G)/\nu _t(G)\le 1.5$.

Regarding the tightness of the conjectured upper bound 2, Tuza [12] noticed that infinitely many extremal graphs exist. Cui et al. [5] characterized planar extremal graphs – they are edge-disjoint unions of $K_4$’s plus possibly some vertices and edges that are not in any triangles. Baron and Kahn [1] proved that Conjecture 1 is asymptotically tight for dense graphs.

Fractional and weighted variants of Conjecture 1 were also studied. Krivelevich [9] confirmed two fractional versions of the conjecture: $\tau _t(G)\le 2\nu ^{*}_t(G)$ and $\tau ^{*}_t(G)\le 2\nu _t(G)$ hold for all graphs G, where $\tau ^{*}_t(G)$ and $\nu ^{*}_t(G)$ are the values of a minimum fractional triangle cover and a maximum fractional triangle packing of G, respectively. The result was generalized by Chapuy et al. [3] to the weighted case, which amounts to packing and covering triangles in multigraphs $G_w$ (obtained from G by adding multiple edges). The authors [3] showed that $\tau _t(G_w)\le 2\nu _t^{*}(G_w)-\sqrt{\nu _t^{*}(G_w)/6}+1$ and $\tau _t^{*}(G_w)\le 2\nu _t(G_w)$; the arguments imply an LP-based 2-approximation algorithm for finding a minimum weighted triangle cover in graph G.

Our Contributions. Along a different line, we establish new sufficient conditions for validity of Conjecture 1 by comparing the triangle packing number, the number of triangles and the number of edges. Given a graph G, we use

$\mathscr {T}_G=\{E(T):T$ is a triangle in $G\}$

to denote the set consisting of the (edge sets of) triangles in G. Without loss of generality, we focus on the graphs where every edge is contained in some triangle. These graphs are called irreducible.

Theorem 1

Let $G=(V,E)$ be an irreducible graph. Then a triangle cover of G with cardinality at most $2\nu _t(G)$ can be found in polynomial time, which implies $\tau _t(G)\le 2\nu _t(G)$, if one of the following conditions is satisfied: (i) $\nu _t(G)/|\mathscr {T}_G|\ge \frac{1}{3}$, (ii) $\nu _t(G)/|E|\ge \frac{1}{4}$, and (iii) $|E|/|\mathscr {T}_G|\ge 2$.

The primary idea behind the theorem is simple: any one of conditions (i) – (iii) allows us to remove at most $\nu _t(G)$ edges from G to make the resulting graph $G'$ satisfy $\tau _t(G')=\nu _t(G')$; the removed edges and the edges in a minimum triangle cover of $G'$ form a triangle cover of G with size at most $\nu _t(G)+\nu _t(G')\le 2\nu _t(G)$. The idea is realized by establishing new results on linear 3-uniform hypergraphs (see Sect. 2); the most important one states that such a hypergraph could be made acyclic by removing a number of vertices that is no more than a third of the number of its edges. A key observation here is that hypergraph $(E,\mathscr {T}_G)$ is linear and 3-uniform.

To show the qualities of conditions (i) – (iii) in Theorem 1, we obtain the following result which complements to the constants $\frac{1}{3}$, $\frac{1}{4}$ and 2 in these conditions with $\frac{1}{4}$, $\frac{1}{5}$ and $\frac{3}{2}$, respectively.

Theorem 2

Conjecture 1 holds for every graph if there exists some real $\delta >0$ such that Conjecture 1 holds for every irreducible graph G satisfying one of the following inequalities: $\nu _t(G)/|\mathscr {T}_G|\ge \frac{1}{4}-\delta$, $\nu _t(G)/|E|\ge \frac{1}{5}-\delta$, and $|E|/|\mathscr {T}_G|\ge \frac{3}{2}-\delta$.

It is worthwhile pointing out that strengthening Theorem 1, our arguments actually establish stronger results for linear 3-uniform hypergraphs.

Theorem 3

Let $\mathcal H=(\mathcal V,\mathcal E)$ be a linear 3-uniform hypergraph without isolated vertices. If $\nu (\mathcal H)/|\mathcal E|\ge \frac{1}{3}$ or $|\mathcal V|/|\mathcal E|\ge 2$, then a transversal of $\mathcal H$ with cardinality at most $2\nu (\mathcal H)$ can be found in polynomial time, which implies $\tau (\mathcal H)\le 2\nu (\mathcal H)$.

The rest of paper is organized as follows. Section 2 proves theoretical and algorithmic results on linear 3-uniform hypergraphs concerning feedback sets, which are main technical tools for establishing new sufficient conditions for Tuza’s conjecture in Sect. 3. Section 4 concludes the paper with extensions and future research directions. Omitted deals and proofs can be found in the full version of the paper [4].

2 Hypergraphs

This section develops hypergraph tools for studying Conjecture 1. The theoretical and algorithmic results are of interest in their own right.

Let $\mathcal H=(\mathcal V,\mathcal E)$ be a hypergraph with vertex set $\mathcal V$ and edge set $\mathcal E$. For convenience, we use $|\!|\mathcal H|\!|$ to denote the number $|\mathcal E|$ of edges in $\mathcal H$. If hypergraph $\mathcal H'=(\mathcal V',\mathcal E')$ satisfies $\mathcal V' \subseteq \mathcal V$ and $\mathcal E' \subseteq \mathcal E$, we call $\mathcal H'$ a sub-hypergraph of $\mathcal H$, and write $\mathcal H'\subseteq \mathcal H$. For each $v\in \mathcal V$, the degree $d_{\mathcal H}(v)$ is the number of edges in $\mathcal E$ that contain v. We say v is an isolated vertex of $\mathcal H$ if $d_{\mathcal H}(v)=0$. Let $k\in \mathbb N$ be a positive integer. Hypergraph $\mathcal H$ is called k-regular if $d_{\mathcal H}(u)=k$ for each $u\in \mathcal V$, and k-uniform if $|e|=k$ for each $e\in \mathcal E$. Hypergraph $\mathcal H$ is linear if $|e\cap f|\le 1$ for any pair of distinct edges $e,f\in \mathcal E$.

A vertex-edge alternating sequence $v_{1}e_{1}v_{2}...v_{k}e_{k}v_{k+1}$ of $\mathcal H$ is called a path (of length k) between $v_{1}$ and $v_{k+1}$ if $v_{1}, v_{2},..., v_{k+1}\in \mathcal V$ are distinct, $e_{1}, e_{2},..., e_{k}\in \mathcal E$ are distinct, and $\{v_{i},v_{i+1}\}\subseteq e_{i}$ for each $i\in [k]=\{1,\ldots ,k\}$. Hypergraph $\mathcal H$ is said to be connected if there is a path between any pair of distinct vertices in $\mathcal H$. A maximal connected sub-hypergraph of $\mathcal H$ is called a component of $\mathcal H$.

A vertex-edge alternating sequence $\mathcal C= v_{1}e_{1}v_{2}e_{2}...v_{k}e_{k}v_{1}$, where $k\ge 2$, is called a cycle (of length k) if $v_{1}, v_{2},..., v_{k}\in \mathcal V$ are distinct, $e_{1}, e_{2},..., e_{k}\in \mathcal E$ are distinct, and $\{v_{i},v_{i+1}\}\subseteq e_{i}$ for each $i\in [k]$, where $v_{k+1}=v_{1}$. We consider the cycle $\mathcal C$ as a sub-hypergraph of $\mathcal H$ with vertex set $\cup _{i\in [k]}e_i$ and edge set $\{e_{i}: i\in [k]\}$. For any $\mathcal S\subset \mathcal V$ (resp. $S\subset \mathcal E$), we write $\mathcal H\setminus \mathcal S$ for the sub-hypergraph of $\mathcal H$ obtained from $\mathcal H$ by deleting all vertices in $\mathcal S$ and all edges incident with some vertices in $\mathcal S$ (resp. deleting all edges in $\mathcal E$ and keeping vertices). If $\mathcal S$ is a singleton set $\{s\}$, we write $\mathcal H\setminus s$ instead of $\mathcal H\setminus \{s\}$. For any $\mathcal S\subseteq 2^{\mathcal V}$, the hypergraph $(\mathcal V,\mathcal E\cup \mathcal S)$ is often written as $\mathcal H\oplus \mathcal S$ if $\mathcal S\cap \mathcal E=\emptyset$.

A vertex (resp. edge) subset of $\mathcal H$ is called a feedback vertex set or FVS (resp. feedback edge set or FES) of $\mathcal H$ if it intersects the vertex (resp. edge) set of every cycle of $\mathcal H$. A vertex subset of $\mathcal H$ is called a transversal of $\mathcal H$ if it intersects every edge of $\mathcal H$. Let $\tau ^{{}_{\mathcal V}}_c(\mathcal H)$, $\tau _c^{{}_{\mathcal E}}(\mathcal H)$ and $\tau (\mathcal H)$ denote, respectively, the minimum cardinalities of a FVS, a FES, and a transversal of $\mathcal H$. A matching of $\mathcal H$ is an nonempty set of pairwise disjoint edges of $\mathcal H$. Let $\nu (\mathcal H)$ denote the maximum cardinality of a matching of $\mathcal H$. It is easy to see that $\tau ^{{}_{\mathcal V}}_c(\mathcal H)\le \tau _c^{{}_{\mathcal E}}(\mathcal H)$, $\tau ^{{}_{\mathcal V}}_c(\mathcal H)\le \tau (\mathcal H)$ and $\nu (\mathcal H)\le \tau (\mathcal H)$. Our discussion will frequently use the trivial observation that if no cycle of $\mathcal H$ contains any element of some subset $\mathcal S$ of $\mathcal V\cup \mathcal E$, then $\mathcal H$ and $\mathcal H\setminus \mathcal S$ have the same set of FVS’s, and $\tau _c^{{}_{\mathcal V}}(\mathcal H)= \tau _c^{{}_{\mathcal V}}(\mathcal H\setminus \mathcal S)$. The following theorem is one of our main contributions.

Theorem 4

Let $\mathcal H$ be a linear 3-uniform hypergraph. Then $\tau _c^{{}_{\mathcal V}}(\mathcal H)\le |\!|\mathcal H|\!|/3$.

Proof

Suppose that the theorem failed. We take a counterexample $\mathcal H=(\mathcal V,\mathcal E)$ with $\tau _c^{{}_{\mathcal V}}(\mathcal H)> |\mathcal E|/3$ such that $|\!|\mathcal H|\!|=|\mathcal E|$ is as small as possible. Obviously $|\mathcal E|\ge 3$. Without loss of generality, we can assume that $\mathcal H$ has no isolated vertices. Since $\mathcal H$ is linear, any cycle in $\mathcal H$ is of length at least 3.

If there exists some $e\in \mathcal E$ which does not belong to any cycle of $\mathcal H$, then $\tau _c^{{}_{\mathcal V}}(\mathcal H)= \tau _c^{{}_{\mathcal V}}(\mathcal H\setminus e)$. The minimality of $\mathcal H=(\mathcal V,\mathcal E)$ implies $\tau _c^{{}_{\mathcal V}}(\mathcal H\setminus e)\le (|\mathcal E|-1)/3$, giving $\tau _c^{{}_{\mathcal V}}(\mathcal H)< |\mathcal E|/3$, a contradiction. So we have

• (1) Every edge in $\mathcal E$ is contained in some cycle of $\mathcal H$.

If there exists some $v\in \mathcal V$ with $d_{\mathcal H}(v)\ge 3$, then $\tau _c^{{}_{\mathcal V}}(\mathcal H\setminus v)\le (|\mathcal E|-d_{\mathcal H}(v))/3\le (|\mathcal E|-3)/3$, where the first inequality is due to the minimality of $\mathcal H$. Given a minimum FVS $\mathcal S$ of $\mathcal H\setminus v$, it is clear that $\mathcal S\cup \{v\}$ is a FVS of $\mathcal H$ with size $|\mathcal S|+1=\tau _c^{{}_{\mathcal V}}(\mathcal H\setminus v)+1\le |\mathcal E|/3$, a contradiction to $\tau _c^{{}_{\mathcal V}}(\mathcal H)> |\mathcal E|/3$. So we have

• (2) $d_{\mathcal H}(v)\le 2$ for all $v\in \mathcal V$.

Suppose that there exists some $v\in \mathcal V$ with $d_{\mathcal H}(v)= 1$. Let $e_1\in \mathcal E$ be the unique edge that contains v. Recall from (1) that $e_1$ is contained in a cycle $\mathcal C= v_{1}e_{1}v_{2}e_{2}v_{3}\cdots e_{k}v_{1}$, where $k\ge 3$. By (2), we have $d_{\mathcal H}(v_i)=2$ for all $i\in [k]$. In particular $d_{\mathcal H}(v_1)=d_{\mathcal H}(v_2)=2>d_{\mathcal H}(v)$ implies $v\not \in \{v_1,v_2\}$, and in turn $v_1,v_2,v \in e_1$ enforces $e_{1}= \{v_{1},v,v_{2}\}$. Let $\mathcal S$ be a minimum FVS of $\mathcal H'=\mathcal H\setminus \{e_1,e_2,e_3\}$. It follows from (2) that

$$\begin{aligned} \mathcal H\setminus v_3\subseteq \mathcal H\setminus \{e_2,e_3\}= \mathcal H'\oplus e_1, \end{aligned}$$

and in $\mathcal H'\oplus e_1$, edge $e_1$ intersects at most one other edge, and therefore is not contained in any cycle. Thus $\mathcal S$ is a FVS of $\mathcal H'\oplus e_1$, and hence a FVS of $\mathcal H\setminus v_3$, implying that $\{v_3\}\cup \mathcal S$ is a FVS of $\mathcal H$. We deduce that $|\mathcal E|/3<\tau _c^{{}_{\mathcal V}}(\mathcal H)\le |\{v_3\}\cup \mathcal S|\le 1+|\mathcal S|$. Therefore $\tau _c^{{}_{\mathcal V}}(\mathcal H')=|\mathcal S|>(|\mathcal E|-3)/3=|\!|\mathcal H'|\!|/3$ shows a contradiction to the minimality of $\mathcal H$. Hence the vertices of $\mathcal H$ all have degree at least 2, which together with (2) gives

• (3) $\mathcal H$ is 2-regular.

Let $\mathcal C=(\mathcal V_c,\mathcal E_c)=v_1e_1v_2e_2\ldots v_ke_kv_1$ be a shortest cycle in $\mathcal H$, where $k\ge 3$. For each $i\in [k]$, suppose that $e_i=\{v_i,u_i,v_{i+1}\}$, where $v_{k+1}=v_1$.

Because $\mathcal C$ is a shortest cycle, for each pair of distinct indices $i,j\in [k]$, we have $e_{i}\cap e_{j}=\emptyset$ if and only if $e_i$ and $e_j$ are not adjacent in $\mathcal C$, i.e., $|i-j|\not \in \{1,k-1\}$. This fact along with the linearity of $\mathcal H$ says that $v_1,v_2,\ldots ,v_k,u_1,u_2,\ldots ,u_k$ are distinct. By (3), each $u_i$ is contained in a unique edge $f_i\in \mathcal E\setminus \mathcal E_c$, $i\in [k]$. We distinguish among three cases depending on the values of $k\pmod 3$. In each case, we construct a proper sub-hypergraph $\mathcal H'$ of $\mathcal H$ with $|\!|\mathcal H'|\!|<|\!|\mathcal H|\!|$ and $\tau _c^{{}_{\mathcal V}}(\mathcal H')>|\!|\mathcal H'|\!|/3$ which shows a contradiction to the minimality of $\mathcal H$.

Case 1. $k\equiv 0\pmod 3$: Let $\mathcal S$ be a minimum FVS of $\mathcal H'=\mathcal H\setminus \mathcal E_c$. Setting $\mathcal V_*=\{v_i:i\equiv 0\pmod 3, i\in [k]\}$ and $\mathcal E_*=\{e_i:i\equiv 1\pmod 3, i\in [k]\}$, it follows from (3) that

$$\begin{aligned} \mathcal H\setminus \mathcal V_*\subseteq (\mathcal H\setminus \mathcal E_c)\oplus \mathcal E_*= \mathcal H'\oplus \mathcal E_*, \end{aligned}$$

and in $\mathcal H'\oplus \mathcal E_*$, each edge in $\mathcal E_*$ intersects exactly one other edge, and therefore is not contained in any cycle. Thus $(\mathcal H'\oplus \mathcal E_*)\setminus \mathcal S$ is also acyclic, so is $(\mathcal H\setminus \mathcal V_*)\setminus \mathcal S$, saying that $\mathcal V_*\cup \mathcal S$ is a FVS of $\mathcal H$. We deduce that $|\mathcal E|/3<\tau _c^{{}_{\mathcal V}}(\mathcal H)\le |\mathcal V_*\cup \mathcal S|\le k/3+|\mathcal S|$. Therefore $\tau _c^{{}_{\mathcal V}}(\mathcal H')=|\mathcal S|>(|\mathcal E|-k)/3=|\!|\mathcal H'|\!|/3$ shows a contradiction.

Case 2. $k\equiv 1\pmod 3$: Consider the case where $f_1\ne f_3$ or $f_2\ne f_4$. Relabeling the vertices and edges if necessary, we may assume without loss of generality that $f_1\ne f_3$. Let $\mathcal S$ be a minimum FVS of $\mathcal H'=\mathcal H\setminus (\mathcal E_c\cup \{f_1,f_3\})$. Set $\mathcal V_*=\emptyset$, $\mathcal E_*=\emptyset$ if $k=4$ and $\mathcal V_*=\{v_i:i\equiv 0\pmod 3, i\in [k]-[3]\}$, $\mathcal E_*=\{e_i:i\equiv 1\pmod 3, i\in [k]-[6]\}$ otherwise. In any case we have $|\mathcal V_*|=(k-4)/3$ and

$$\begin{aligned} \mathcal H\setminus (\{u_1,u_3\}\,\cup \,\mathcal V_*)\subseteq (\mathcal H\setminus (\mathcal E_c\,\cup \,\{f_1,f_3\}))\,\oplus \,( \{e_2,e_4\}\,\cup \,\mathcal E_*)= \mathcal H'\,\oplus \, (\{e_2,e_4\}\,\cup \,\mathcal E_*). \end{aligned}$$

Note from (3) that in $\mathcal H'\oplus (\{e_2,e_4\}\,\cup \,\mathcal E_*)$, each edge in $\{e_2,e_4\}\,\cup \,\mathcal E_*$ can intersect at most one other edge, and therefore is not contained in any cycle. Thus $( \mathcal H'\oplus (\{e_2,e_4\}\,\cup \,\mathcal E_*))\setminus \mathcal S$ is also acyclic, so is $(\mathcal H\setminus (\{u_1,u_3\}\,\cup \,\mathcal V_*))\setminus \mathcal S$. Thus $\{u_1,u_3\}\,\cup \,\mathcal V_*\,\cup \,\mathcal S$ is a FVS of $\mathcal H$, and $|\mathcal E|/3<\tau _c^{{}_{\mathcal V}}(\mathcal H)\le |\{u_1,u_3 \}\,\cup \,\mathcal V_*\,\cup \,\mathcal S|\le 2\,+\,|\mathcal V_*|\,+\,|\mathcal S|\,=\,(k\,+\,2)/3\,+\,|\mathcal S|$. This gives $\tau _c^{{}_{\mathcal V}}(\mathcal H')=|\mathcal S|>(|\mathcal E|-k-2)/3=|\mathcal H'|/3$, a contradiction.

Consider the case where $f_1= f_3$ and $f_2=f_4$. As $u_1,u_2,u_3,u_4$ are distinct and $|f_1|=|f_2|=3$, we have $f_1\ne f_2$. Observe that $u_1e_1v_2e_2v_3e_3u_3f_3u_1$ is a cycle in $\mathcal H$ of length 4. The minimality of k enforces $k=4$. Therefore $\mathcal E_c\cup \{f_1,f_2\}$ consist of 6 distinct edges. Let $\mathcal S$ be a minimum FVS of $\mathcal H'=\mathcal H\setminus (\mathcal E_c\cup \{f_1,f_2\})$. It follows from (3) that

$$\begin{aligned} \mathcal H\setminus \{u_2,u_4\}\subseteq (\mathcal H\setminus (\mathcal E_c\cup \{f_1,f_2\}))\oplus \{e_1,e_3,f_1\}= \mathcal H'\oplus \{e_1,e_3,f_1\}. \end{aligned}$$

In $\mathcal H'\oplus \{e_1,e_3,f_1\}$, both $e_{1}$ and $e_{3}$ intersect only one other edge, which is $f_1$, and any cycle through $f_1$ must contain $e_1$ or $e_3$. It follows that none of $e_1,e_3,f_1$ is contained by a cycle of $\mathcal H'\oplus \{e_1,e_3,f_1\}$. Thus $(\mathcal H'\oplus \{e_1,e_3,f_1\})\setminus \mathcal S$ is acyclic, so is $(\mathcal H \setminus \{u_2,u_4\})\setminus \mathcal S$, saying that $\{u_2,u_4\}\cup \mathcal S$ is a FVS of $\mathcal H$. Hence $|\mathcal E|/3<\tau _c^{{}_{\mathcal V}}(\mathcal H)\le |\{u_2,u_4 \}\cup \mathcal S|\le 2+ |\mathcal S|$. In turn $\tau _c^{{}_{\mathcal V}}(\mathcal H')=|\mathcal S|>(|\mathcal E|-6)/3=|\!|\mathcal H'|\!|/3$ shows a contradiction.

Case 3. $k\equiv 2\pmod 3$: Let $\mathcal S$ be a minimum FVS of $\mathcal H'=\mathcal H\setminus (\mathcal E_c\cup \{f_1\})$. Setting $\mathcal V_*=\{v_i:i\equiv 1\pmod 3, i\in [k]-[3]\}$ and $\mathcal E_*=\{e_i:i\equiv 2\pmod 3, i\in [k]\}$, we have $|\mathcal V_*|=(k-2)/3$ and

$$\begin{aligned} \mathcal H\setminus (\{u_1\}\cup \mathcal V_*)\subseteq (\mathcal H\setminus (\mathcal E_c\cup \{f_1\}))\oplus \mathcal E_*= \mathcal H'\oplus \mathcal E_* \end{aligned}$$

In $\mathcal H'\,\oplus \,\mathcal E_*$, each edge in $\mathcal E_*$ intersects at most one other edge, and therefore is not contained in any cycle. Thus $(\mathcal H'\,\oplus \,\mathcal E_*)\setminus \mathcal S$ is acyclic, so is $(\mathcal H\setminus ( \{u_1\}\cup \mathcal V_*))\setminus \mathcal S$. Hence $\{u_1\}\,\cup \,\mathcal V_*\,\cup \,\mathcal S$ is a FVS of $\mathcal H$, yielding $|\mathcal E|/3<\tau _c^{{}_{\mathcal V}}(\mathcal H)\le | \{u_1\}\,\cup \,\mathcal V_*\,\cup \,\mathcal S|\le 1+(k-2)/3+|\mathcal S|$ and a contradiction $\tau _c^{{}_{\mathcal V}}(\mathcal H')=|\mathcal S|>(|\mathcal E|-k-1)/3=|\!|\mathcal H'|\!|/3$.

The combination of the above three cases complete the proof.   $\square$

The upper bound $|\!|\mathcal H|\!|/3$ in Theorem 4 is best possible. See Fig. 1 for illustrations of five linear 3-uniform hypergraphs attaining the upper bound. It is easy to prove that the maximum degree of every extremal hypergraph (those $\mathcal H$ with $\tau _c^{{}_{\mathcal V}}(\mathcal H)= |\!|\mathcal H|\!|/3$) is at most three. Despite a number of attempts, we did not find any extremal hypergraph other than those in Fig. 1. It would be interesting to characterize all extremal hypergraphs for Theorem 4.

Fig. 1.

Some linear 3-uniform hypergraphs $\mathcal H$ with $\tau _c^{{}_{\mathcal V}}(\mathcal H)= |\!|\mathcal H|\!|/3$.

The proof of Theorem 4 actually gives a recursive combinatorial algorithm (Algorithm 1) for finding in polynomial time a FVS of size at most $|\!|\mathcal H|\!|/3$ on a linear 3-uniform hypergraph $\mathcal H$.

Note that Algorithm 1 never visits isolated vertices (it only scans along the edges of the current hypergraph). The number of iterations performed by the algorithm is upper bounded by $|\mathcal E|$. Since $\mathcal H$ is 3-uniform, the condition in any step is checkable in $O(|\mathcal E|^2)$ time. One can use the breadth first search algorithm to find a cycle in stated in Step 7 or Step 9 in $O(|\mathcal E|^2)$ time. Thus Algorithm 1 runs in $O(|\mathcal E|^3)$ time.

Corollary 1

Given any linear 3-uniform hypergraph $\mathcal H$, Algorithm 1 finds in $O(|\!|\mathcal H|\!|^3)$ time a FVS of $\mathcal H$ with size at most $|\!|\mathcal H|\!|/3$.   $\square$

Corollary 1 concerns with small FVS of linear 3-uniform hypergraphs. Next, we consider the counterpart of FES.

Lemma 1

If $\mathcal H=(\mathcal V,\mathcal E)$ is a connected linear 3-uniform hypergraph without cycles, then $|\mathcal V|=2|\mathcal E|+1$.

Proof

We prove by induction on $|\mathcal E|$. The base case where $|\mathcal E|=0$ is trivial. Inductively, we assume that $|\mathcal E|\ge 1$ and the lemma holds for all connected acyclic linear 3-uniform hypergraph of edges fewer than $\mathcal H$. Take arbitrary $e\in \mathcal E$. Since $\mathcal H$ is connected, acyclic and 3-uniform, $\mathcal H\setminus e$ contains exactly three components $\mathcal H_{i}=(\mathcal V_{i},\mathcal E_{i})$, $i=1,2,3$. Note that for each $i\in [3]$, hypergraph $\mathcal H_i$ with $|\mathcal E_i|<|\mathcal E|$ is connected, linear, 3-uniform and acyclic. By the induction hypothesis, we have $|\mathcal V_{i}|=2|\mathcal E_{i}|+1$ for $i=1,2,3$. It follows that $|\mathcal V|=\sum _{i=1}^3|\mathcal V_{i}|= 2\sum _{i=1}^3|\mathcal E_{i}| +3= 2|\mathcal E|+1$.   $\square$

Given any hypergraph $\mathcal H=(\mathcal V,\mathcal E)$, we can easily find a minimal (not necessarily minimum) FES in $O(|\mathcal E|^2)$ time: Go through the edges of the trivial FES $\mathcal E$ in any order, and remove the edge from the FES immediately if the edge is redundant. The redundancy test can be implemented using Depth First Search.

Lemma 2

Let $\mathcal H=(\mathcal V,\mathcal E)$ be a linear 3-uniform hypergraph with p components. If $\mathcal F$ is a minimal FES of $\mathcal H$, then $|\mathcal F|\le 2|\mathcal E|-|\mathcal V|+p$. In particular, $\tau _c^{{}_{\mathcal E}}(\mathcal H)\le 2|\mathcal E|-|\mathcal V|+p$.

Proof

Suppose that $\mathcal H\setminus \mathcal F$ contains exactly k components $\mathcal H_{i}=(\mathcal V_{i},\mathcal E_{i})$, $i=1,\ldots ,k$. It follows from Lemma 1 that $|\mathcal V_{i}|=2|\mathcal E_{i}|+1$ for each $i\in [k]$. Thus $|\mathcal V|=\sum _{i\in [k]}|\mathcal V_{i}|= 2\sum _{i\in [k]}|\mathcal E_{i}|+k= 2(|\mathcal E|- |\mathcal F|)+k$, which means $2|\mathcal F|= 2|\mathcal E|-|\mathcal V|+k$. To establish the lemma, it suffices to prove $k\le |\mathcal F|+ p$.

In case of $|\mathcal F|=0$, we have $\mathcal F=\emptyset$ and $k=p=|\mathcal F|+p$. In case of $|\mathcal F| \ge 1$, suppose that $\mathcal F=\{e_{1},...,e_{|\mathcal F|}\}$. Because $\mathcal F$ is a minimal FES of $\mathcal H$, for each $i\in [|\mathcal F|]$, there is a cycle $\mathcal C_{i}$ in $\mathcal H\setminus (\mathcal F\setminus \{e_{i}\})$ such that $e_{i}\in \mathcal C_{i}$, and $\mathcal C_i\setminus e_i$ is a path in $\mathcal H\setminus \mathcal F$ connecting two of the three vertices in $e_i$. Considering $\mathcal H\setminus \mathcal F$ being obtained from $\mathcal H$ be removing $e_1,e_2,\ldots ,e_{|\mathcal F|}$ sequentially, for $i=1,\ldots ,|\mathcal F|$, since $|e_i|=3$, the presence of path $\mathcal C_i\setminus e_i$ implies that the removal of $e_i$ can create at most one more component. Therefore we have $k\le p+|\mathcal F|$ as desired.   $\square$

Given a hypergraph $\mathcal H$, let $M_{\mathcal H}$ be the $\mathcal V\times \mathcal E$ incidence matrix. If $\mathcal H$ is acyclic, then $M_{\mathcal H}$ falls within the class of restricted totally unimodular matrices, and a minimum transversal and a maximum matching of $\mathcal H$ can be found using Yanakakis’s combinatorial algorithm [13] based on the current best combinatorial algorithms for the b-matching problem and the maximum weighted independent set problem on bipartite multigraphs [10].

Theorem 5

([2, 13]). Let $\mathcal H$ be a hypergraph with n non-isolated vertices and m edges. If $\mathcal H$ has no cycle, then $\tau (\mathcal H)=\nu (\mathcal H)$, and a minimum transversal and a maximum matching of $\mathcal H$ can be found in $O(n(m+n\log n)\log n)$ time.   $\square$

3 Triangle Packing and Covering

This section establishes several new sufficient conditions for Conjecture 1, and provides their algorithmic implications on finding small triangle covers. Section 3.1 deals with graphs of high triangle packing numbers. Section 3.2 investigates irreducible graphs with many edges.

To each graph $G=(V,E)$, we associate a hypergraph $\mathcal H_G=(E,\mathscr {T}_G)$, referred to as triangle hypergraph of G. Since G is simple, it is easy to see that $\mathcal H_G$ is 3-uniform and linear, $\nu (\mathcal H_G)=\nu _{t}(G)$ and $\tau (\mathcal H_G)=\tau _{t}(G)$. Note that $|\!|\mathcal H_G|\!|=|\mathscr {T}_G|<\min \{|V|^3,|E|^3\}$, and $|E|\le 3|\mathscr {T}_G|$ if G is irreducible, i.e., $\cup _{T\in \mathscr {T}_G}E(T)=E$. Note that the number of non-isolated vertices of $\mathcal H_G$ is upper bounded by $3|\!|\mathcal H_G|\!|=3|\mathscr {T}_G|$.

3.1 Graphs with Many Edge-Disjoint Triangles

We investigate Conjecture 1 for graphs with large triangle packing numbers, which are firstly compared with the number of triangles, and then with the number of edges.

Theorem 6

If a graph G and a real number $c\in (0,1]$ satisfy $\nu _{t}(G)/|\mathscr {T}_G|\ge c$, then a triangle cover of G with size at most $\frac{3c+1}{3c}\nu _t(G)$ can be found in $O(|\mathscr {T}_G|^3)$ time, which implies $\tau _t(G)/\nu _t(G)\le 1+\frac{1}{3c}$.

Proof

We consider the triangle hypergraph $\mathcal H_G=(E,\mathscr {T}_G)$ of G which is 3-uniform and linear. By Corollary 1, we can find in $O(|\mathscr {T}_G|^3)$ time a FVS $\mathcal S$ of $\mathcal H_G$ with $|\mathcal S|\le |\mathscr {T}_G|/3$. Since $\nu (\mathcal H_G)=\nu _{t}(G)\ge c|\mathscr {T}_G|$, it follows that $|\mathcal S|\le \nu (\mathcal H_G)/(3c)$. As $\mathcal H_G\setminus \mathcal S$ is acyclic, Theorem 5 enables us to find in $O(|\mathscr {T}_G|^2\log ^2|\mathscr {T}_G|)$ time a minimum transversal $\mathcal R$ of $\mathcal H_G\setminus S$ such that $|\mathcal R|=\tau (\mathcal H_G\setminus S)=\nu (\mathcal H_G\setminus \mathcal S)$. We observe that $\mathcal S\cup \mathcal R\subseteq E$ and $G\setminus (\mathcal S\cup \mathcal R)$ is triangle-free. Hence $\mathcal S\cup \mathcal R$ is a triangle cover of G with size

$$|\mathcal S\cup \mathcal R| \le \frac{\nu (\mathcal H_G)}{3c}+\nu (\mathcal H_G\setminus \mathcal S) \le \frac{3c+1}{3c}\nu (\mathcal H_G)=\frac{3c+1}{3c}\nu _t(G),$$

which proves the theorem.   $\square$

The special case of $c=1/3$ in the above theorem gives the following result providing a new sufficient condition for Conjecture 1.

Corollary 2

If graph G satisfies $\nu _{t}(G)/|\mathscr {T}_G|\ge 1/3$, then $\tau _t(G)/\nu _t(G)\le 2$.   $\square$

The mapping from the lower bound c in the condition $\nu _{t}(G)/|\mathscr {T}_G|\ge c$ to the upper bound $1+\frac{1}{3c}$ in the conclusion $\tau _t(G)/\nu _t(G)\le 1+\frac{1}{3c}$ of Theorem 6 shows a kind of trade-off. In Corollary 2, $c = \frac{1}{3}$ maps to $1+\frac{1}{3c} = 2$ hitting the boundary of Conjecture 1. It remains to study graphs G with $\nu _t(G)/|\mathscr {T}_G|<\frac{1}{3}$. The next theorem (Theorem 7) says that we only need to take care of graphs G with $\nu _t(G)/|\mathscr {T}_G|\in (\frac{1}{4}-\epsilon ,\frac{1}{3})$, where $\epsilon$ can be any arbitrarily small positive number. So, in some sense, to settle Conjecture 1, we only have a gap of $\frac{1}{3}-\frac{1}{4}=\frac{1}{12}$ to be bridged. Interestingly, for $c = \frac{1}{4}$, we have $1+\frac{1}{3c} = \frac{7}{3} = 2.333...$, which is much better than the best known general bound 2.87 due to Haxell [7].

Theorem 7

If there exists some real $\delta >0$ such that Conjecture 1 holds for every graph G with $\nu _t(G)/|\mathscr {T}_G|\ge 1/4-\delta$, then Conjecture 1 holds for every graph.

Proof

If $\delta \ge \frac{1}{4}$, the theorem is trivial. We consider $0< \delta < \frac{1}{4}$. As the set of rational numbers is dense, we may assume $\delta \in \mathbb Q$ and $1/4-\delta =i/j$ for some $i,j\in \mathbb N$. Therefore $i/j<1/4$ gives $4i+1\le j$, i.e., $4+1/i\le j/i$. It remains to prove that for any graph G with $\nu _t(G)<(i/j)|\mathscr {T}_G|$ there holds $\tau _t(G)\le 2\nu _t(G)$.

Write k for the positive integer $i|\mathscr {T}_G|-j\cdot \nu _t(G)$. Let $G'$ be the disjoint union of G and k copies of $K_4$. Clearly, $|\mathscr {T}_{G'}|=|\mathscr {T}_G|+k|\mathscr {T}_{K_4}|=|\mathscr {T}_G|\,+\,4k$, $\tau _t(G')=\tau _t(G)\,+\,k\cdot \tau _t(K_4)=\tau _t(G)\,+\,2k$ and $\nu _t(G')=\nu _t(G)\,+\,k\cdot \nu _t(K_4)=\nu _t(G)+k$. It follows that

$$\begin{aligned} (i/j)|\mathscr {T}_{G'}|= & {} (i/j)(|\mathscr {T}_G|+4k)\\= & {} (i/j)((k+j\cdot \nu _t(G))/i+4k)\\= & {} (i/j)(j\cdot \nu _t(G)/i+(4+1/i){k})\\\le & {} \nu _t(G)+k\\= & {} \nu _t(G') \end{aligned}$$

where the inequality is guaranteed by $4+1/i\le j/i$. So $\nu _t(G')\ge (1/4-\delta )|\mathscr {T}_{G'}|$ together with the hypothesis of the theorem implies $\tau _t(G')\le 2\nu _t(G')$, i.e., $\tau _t(G)+2k\le 2(\nu _t(G)+k)$, giving $\tau _t(G)\le 2\nu _t(G)$ as desired.   $\square$

Next, we discuss the sufficient condition that compares the triangle packing number with the number of edges. It is based on the fact that every graph G can be made bipartite (and thus triangle-free) in polynomial time by removing at most half of its edges. Therefore $\tau _t(G)\le |E(G)|/2$, which implies the following result.

Corollary 3

If $G=(V,E)$ is a graph such that $\nu _{t}(G)/|E|\ge c$ for some $c>0$, then $\tau _t(G)/\nu _t(G)\le 1/(2c)$. In particular, if $\nu _{t}(G)/|E|\ge 1/4$, then $\tau _t(G)/\nu _t(G)\le 2$.   $\square$

Thus if $\nu _{t}(G)/|E|\ge c$ for some $c>0$, then a triangle cover of G with size at most $\nu _t(G)/(2c)$ can be found in polynomial time. Complementary to Corollary 2 whose condition $\nu _{t}(G)/|\mathscr {T}_G|\ge 1/3$ mainly takes care of sparse graphs, the second statement of Corollary 3 applies to many dense graphs, including complete graphs on 25 or more vertices.

Similar to Corollary 2 and Theorem 7, by which our future investigation space on Conjecture 1 shrinks to interval $(\frac{1}{4}-\epsilon ,\frac{1}{3})$ w.r.t. $\nu _t(G)/|\mathscr {T}_G|$, Corollary 3 and the following Theorem 8 narrow the interval w.r.t. $\nu _t(G)/|E|$ to $(\frac{1}{5}-\epsilon ,\frac{1}{4})$. Moreover, when taking $c = \frac{1}{5}$ in Corollary 3. we obtain $\frac{1}{2c} = 2.5$, still better than the general bound 2.87 of Haxell [7].

Theorem 8

If there exists some real $\delta >0$ such that Conjecture 1 holds for every graph G with $\nu _t(G)/|E|\!\ge \!1/5-\delta$, then Conjecture 1 holds for every graph.    $\square$

Proof

We use the similar trick to that in proving Theorem 7; we add a number of complete graphs on five (instead of four) vertices. We may assume $\delta \in (0,\frac{1}{5})\cap \mathbb Q$ and $1/5-\delta =i/j$ for some $i,j\in \mathbb N$. Therefore $i/j<1/5$ and the integrality of i, j imply $5+1/i\le j/i$. To prove Conjecture 1 for each graph G with $\nu _t(G)<(i/j)|E|$, we write $k=i|E|-j\cdot \nu _t(G)\in \mathbb N$. Let $G'=(V',E')$ be the disjoint union of G and k copies of $K_5$’s. Then $|E'|=|E|+10k$, $\tau _t(G')=\tau _t(G)+k\cdot \tau _t(K_5)=\tau _t(G)+4k$, $\nu _t(G')=\nu _t(G)+k\cdot \nu _t(K_5)=\nu _t(G)+2k$, and

$$(i/j)|E'|=(i/j)(|E|\,+\,10k) =(i/j)(j\cdot \nu _t(G)/i\,+\,(10\,+\,1/i)k)\le \nu _t(G)\,+\,2k= \nu _t(G')$$

where the inequality is guaranteed by $10+1/i\le 2j/i$. So $\nu _t(G')\ge (1/5-\delta )|E'|$ together with the hypothesis the theorem implies $\tau _t(G')\le 2\nu _t(G')$, i.e., $\tau _t(G)+4k\le 2(\nu _t(G)+2k)$, giving $\tau _t(G)\le 2\nu _t(G)$ as desired.   $\square$

3.2 Graphs with Many Edges on Triangles

Each graph has a unique maximum irreducible subgraph. Conjecture 1 is valid for a graph if and only the conjecture is valid for its maximum irreducible subgraph. In this section, we study sufficient conditions for Conjecture 1 on irreducible graphs that bound the number of edges from below in terms of the number of triangles.

Theorem 9

If $G=(V,E)$ is an irreducible graph such that $|E|/|\mathscr {T}_G|\ge 2$, then a triangle cover of G with cardinality at most $2\nu _t(G)$ can be found in $O(|\mathscr {T}_G|^2\log ^2|\mathscr {T}_G|)$ time, which implies $\tau _t(G)/\nu _t(G)\le 2$.

Proof

Let p be the number of components of the linear 3-uniform hypergraph $\mathcal H=(E,\mathscr {T}_G)$ associated to G. By Lemma 2, we can find in $O(|\mathscr {T}_G|^2)$ time a minimal FES $\mathcal F$ of $\mathcal H$ such that $|\mathcal F|\le 2|\mathscr {T}_G|-|E|+p\le p$. Since G is irreducible, we see that $\mathcal H$ has no isolated vertices, i.e., every component of $\mathcal H$ has at least one edge. Thus $\nu (\mathcal H)\ge p\ge |\mathcal F|$. For the acyclic hypergraph $\mathcal H\setminus \mathcal F$, By Lemma 5 we may found in $O(|\mathscr {T}_G|^2\log ^2|\mathscr {T}_G|)$ time a minimum transversal $\mathcal R$ of $\mathcal H\setminus \mathcal F$ such that

$$\begin{aligned} |\mathcal R|=\tau (\mathcal H\setminus \mathcal F)=\nu (\mathcal H\setminus \mathcal F). \end{aligned}$$

Observe that $\mathcal R\subseteq E$ and $\mathcal F\subseteq \mathscr {T}_G$. If $\mathcal F=\emptyset$, set $\mathcal S=\emptyset$, else for each $F\in \mathcal F$, take $e_F\in E$ with $e_F\in F$, and set $\mathcal S=\{e_F:F\in \mathcal F\}$. It is clear that $\mathcal R\cup \mathcal S$ is a transversal of $\mathcal H$ (i.e., a triangle cover of G) with cardinality $|\mathcal R\cup \mathcal S|\le \nu ( \mathcal H\setminus \mathcal F)+ |\mathcal F| \le 2\nu (\mathcal H)=2\nu _t(G)$, establishing the theorem.   $\square$

We observe that the graphs G that consist of a number of triangles sharing a common edge satisfy $|E(G)|\ge 2|\mathscr {T}_G|$, and $\nu _{t}(G)< |\mathscr {T}_{G}|/3$ when $|\mathscr {T}_{G}|\ge 4$. So in some sense, Theorem 9 works as a supplement of Corollary 2 for sparse graphs.

Along the same line as in the previous subsection, Theorem 9 and the following Theorem 10 jointly narrow the interval w.r.t. $|E(G)|/|\mathscr {T}_G|$ to $(1.5-\epsilon ,2)$ for future study of Conjecture 1 on graph G.

Theorem 10

If there exists some real $\delta >0$ such that Conjecture 1 holds for every irreducible graph $G=(V,E)$ with $|E|/|\mathscr {T}_G|\ge 3/2-\delta$, then Conjecture 1 holds for every graph.   $\square$

4 Conclusion

Using tools from hypergraphs, we design polynomial-time combinatorial algorithms for finding a small triangle covers in graphs, which particularly imply several sufficient conditions for Conjecture 1. The high level idea of these algorithms is to remove some edges from G so that the triangle hypergraph of the remaining graph is acyclic (see the proofs of Theorems 4 and 9), which guarantees that the remaining graph has equal triangle covering number and triangle packing number, and a minimum triangle cover of the remaining graph is computable in polynomial time (see Theorem 5). It is well-known that the acyclic condition in Theorem 5 could be weakened to odd-cycle-freeness [13]. So our sufficient conditions could be (significantly) improved if we can remove (much) fewer edges from G such that the triangle hypergraph of the remaining graph is odd-cycle free.