Covering Triangles in Edge-Weighted Graphs

Abstract

Let G = (V, E) be a simple graph and $\mathbf {w}\in \mathbb {Z}^{E}_{>0}$ assign each edge e ∈ E a positive integer weight w(e). A subset of E that intersects every triangle of G is called a triangle cover of (G, w), and its weight is the total weight of its edges. A collection of triangles in G (repetition allowed) is called a triangle packing of (G, w) if each edge e ∈ E appears in at most w(e) members of the collection. Let τ _t (G, w) and ν _t (G, w) denote the minimum weight of a triangle cover and the maximum cardinality of a triangle packing of (G, w), respectively. Generalizing Tuza’s conjecture for unit weight, Chapuy et al. conjectured that τ _t (G, w)/ν _t (G, w) ≤ 2 holds for every simple graph G and every $\mathbf {w}\in \mathbb {Z}^{E}_{>0}$. In this paper, using a hypergraph approach, we design polynomial-time combinatorial algorithms for finding triangle covers of small weights. These algorithms imply new sufficient conditions for the conjecture of Chapuy et al. More precisely, given (G, w), suppose that all edges of G are covered by the set ${\mathscr {T}}_{G}$ consisting of edge sets of triangles in G. Let $|E|_{w}={\sum }_{e\in E}w(e)$ and $|{\mathscr {T}}_{G}|_{w}={\sum }_{\{e,f,g\}\in {\mathscr {T}}_{G}}w(e)w(f)w(g)$ denote the weighted numbers of edges and triangles in (G, w), respectively. We show that a triangle cover of (G, w) of weight at most 2ν _t (G, w) can be found in strongly polynomial time if one of the following conditions is satisfied: (i) $\nu _{t}(G,\mathbf {w})/|{\mathscr {T}}_{G}|_{w}\ge \frac {1}{3}$, (ii) $\nu _{t}(G,\mathbf {w})/|E|_{w}\ge \frac {1}{4}$, (iii) $|E|_{w}/|{\mathscr {T}}_{G}|_{w}\ge 2$.

1 Introduction

Graphs considered in this paper are undirected, finite and may have multiple edges. Given a graph G = (V, E) with vertex set V (G) = V and edge set E(G) = E, a triangle in G is a 3-vertex complete subgraph. 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 τ _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 ν _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 ≤ τ _t (G)/ν _t (G) ≤ 3 holds for every graph G. Our research is motivated by the following conjecture of Tuza [1], and its weighted generalization of Chapuy et al. [2].

Conjecture 1.1 (Tuza’s Conjecture [1])

τ _t (G)/ν _t (G) ≤ 2 holds for every simple graph G.

To the best of our knowledge, the conjecture is still unsolved in general. If it is true, then the upper bound 2 is sharp as shown by K₄ and K₅ – the complete graphs of orders 4 and 5.

Related work

The only known universal upper bound smaller than 3 was given by Haxell [3], who showed that τ _t (G)/ν _t (G) ≤ 66/23 = 2.8695… holds for all simple graphs G. Haxell’s proof [3] implies a polynomial-time algorithm for finding a triangle cover of cardinality at most 66/23 times that of a maximal triangle packing. Other partial results on Tuza’s conjecture concern special classes of graphs.

Tuza [4] proved his conjecture holds for planar simple graphs, K₅-free chordal simple graphs, and simple graphs with n vertices and at least 7n²/16 edges. The proof for planar graphs [4] gives an elegant polynomial-time algorithm for finding a triangle cover in planar simple graphs with cardinality at most twice that of a maximal triangle packing. The validity of Tuza’s conjecture on the class of planar graphs was later generalized by Krivelevich [5] to the class of simple graphs without K_3,3-subdivision. Haxell and Kohayakawa [6] showed that τ _t (G)/ν _t (G) ≤ 2 − 𝜖 for tripartite simple graphs G, where 𝜖 is about 0.044. Haxell, Kostochka and Thomassé [7] proved that every K₄-free planar simple graph G satisfies τ _t (G)/ν _t (G) ≤ 1.5.

Regarding the tightness of the conjectured upper bound 2, Tuza [4] noticed that infinitely many simple graphs G attain the conjectured upper bound τ _t (G)/ν _t (G) = 2. Cui, Haxell and Ma [8] characterized planar simple graphs G satisfying τ _t (G)/ν _t (G) = 2; these graphs are edge-disjoint unions of K₄’s plus possibly some vertices and edges that are not in triangles. Baron and Kahn [9] proved that Tuza’s conjecture is asymptotically tight for dense simple graphs.

Fractional and weighted variants of Conjecture 1.1 were studied in literature. Krivelevich [5] proved two fractional versions of the conjecture: $\tau _{t}(G)\leq 2\nu ^{\ast }_{t}(G)$ and $\tau ^{\ast }_{t}(G)\leq 2\nu _{t}(G)$, where $\tau ^{\ast }_{t}(G)$ and $\nu ^{\ast }_{t}(G)$ are the values of an optimal fractional triangle cover and an optimal fractional triangle packing of simple graph G, respectively. The result was generalized by Chapuy et al. [2] to the weighted version. Given a simple graph G and a positive integer edge weight function $\mathbf {w}\in \mathbb {Z}_{>0}^{E(G)}$, the weight of any subset S of E(G) is the total weight of its edges. A triangle packing of (G, w) refers to a collection of triangles in G (repetition allowed) such that each edge e ∈ E(G) appears in at most w(e) members of the collection. Let τ _t (G, w) and ν _t (G, w) denote the minimum weight of a triangle cover and the maximum cardinality of a triangle packing of (G, w), respectively. The values of τ _t (G, w) and ν _t (G, w) are often referred to as the weighted triangle covering number and weighted triangle packing number of G, respectively. Observe that 1 ≤ τ _t (G, w)/ν _t (G, w) ≤ 3 holds for every weighted graph (G, w). Chapuy et al. [2] studied the following weighted (version of) Tuza’s conjecture:

Conjecture 1.2 ([2])

τ _t (G, w)/ν _t (G, w) ≤ 2 holds for every simple graph G and every weight function $\mathbf {w}\in \mathbb {Z}_{>0}^{E(G)}$.

The authors [2] showed that $\tau _{t}(G,\mathbf {w})\leq 2\nu _{t}^{\ast }(G,\mathbf {w})-\sqrt {\nu _{t}^{\ast }(G,\mathbf {w})/6}+ 1$ and $\tau _{t}^{\ast }(G,\mathbf {w})\leq 2\nu _{t}(G,\mathbf {w})$, where $\tau ^{\ast }_{t}(G,\mathbf {w})$ and $\nu ^{\ast }_{t}(G,\mathbf {w})$ are the (equal) values of an optimal fractional triangle cover and an optimal fractional triangle packing of (G, w), respectively, for which $\tau _{t}(G,\mathbf {w}) \ge \tau _{t}^{\ast }(G,\mathbf {w}) = \nu _{t}^{\ast }(G,\mathbf {w}) \ge \nu _{t}(G,\mathbf {w})$ is guaranteed by the linear programming (LP) duality. Their arguments imply an LP-based 2-approximation algorithm for finding a minimum weighted triangle cover.

Our contributions

Along a different line, we establish new sufficient conditions for validity of (weighted) Tuza’s conjecture by comparing the (weighted) triangle packing number, the (weighted) number of triangles and the (weighted) number of edges in graphs.

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 in which every edge is contained in some triangle. These graphs are called irreducible.

Theorem 1.3

Let G = (V, E) be an irreducible graph. Then a triangle cover of G with cardinality at most 2ν _t (G) can be found in polynomial time, which implies τ _t (G) ≤ 2ν _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}$ ,

• (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 ν _t (G) edges from G to make the resulting graph G^′ satisfy τ _t (G^′) = ν _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 ν _t (G) + ν _t (G^′) ≤ 2ν _t (G). The idea is realized by establishing new results on (linear) 3-uniform hypergraphs (see Section 2); the most important one states that such a hypergraphs 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 3-uniform, and it is linear when G is simple.

It is worthwhile pointing out that strengthening Theorem 1.3, our arguments actually establish stronger results for 3-uniform hypergraphs (see Theorem 4.1).

Theoretically, weighted triangle packing and covering in (G, w) amounts to (unweighted) triangle packing and covering in multigraph G _w which is obtained from G by replacing each edge e ∈ E(G) with a number w(e) of multiple edges.¹ However, from an algorithmic point of view, polynomial-time solvability of triangle packing and covering in G _w does not necessarily imply the same for (G, w). By more careful consideration on edge weights and utilization of unique properties of $(E,{\mathscr {T}}_{G})$, we ensure strong polynomial-time computation for weighted graphs.

Theorem 1.4

Let G = (V, E) be an irreducible simple graph, $\mathbf {w}\in \mathbb {Z}_{>0}^{E}$,$|E|_{w}={\sum }_{e\in E}w(e)$ and$|{\mathscr {T}}_{G}|_{w}={\sum }_{\{e,f,g\}\in {\mathscr {T}}_{G}}w(e)w(f)w(g)$. Then a triangle cover of (G, w) with weight at most 2ν _t (G, w) can be found in strongly polynomial time, which implies τ _t (G, w) ≤ 2ν _t (G, w) , if one of the following conditions is satisfied:

• (i) $\nu _{t}(G,\mathbf {w})/|{\mathscr {T}}_{G}|_{w}\ge \frac {1}{3}$ ,

• (ii) $\nu _{t}(G,\mathbf {w})/|E|_{w}\ge \frac {1}{4}$ ,

• (iii) $|E|_{w}/|{\mathscr {T}}_{G}|_{w}\ge 2$ .

When w = 1, Theorem 1.4 is nothing but Theorem 1.3. To show the quality of conditions (i) – (iii) in Theorems 1.3 and 1.4, 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 15$ and $\frac 32$, respectively.

Theorem 1.5

Tuza’s conjecture holds for every simple graph (resp. multigraph) if there exists some real δ > 0 such that Tuza’s conjecture holds for every irreducible simple graph (resp. multigraph) G satisfying one of the following properties:

• (i’) $\nu _{t}(G)/|{\mathscr {T}}_{G}|\ge \frac {1}{4}-\delta$ ,

• (ii’) $\nu _{t}(G)/|E|\ge \frac 15-\delta$ ,

• (iii’) $|E|/|{\mathscr {T}}_{G}|\ge \frac 32-\delta$ .

Note that the statement of Theorem 1.5 for multigraphs can be converted to an equivalent weighted version concerning with edge-weighted simple graphs.

This paper turns out to be a complete generalization and strengthening of the recent work on unweighted simple graphs [10]. In the present paper, we study triangle packing and covering not only for general multigraphs, but also for weighted simple graphs from an algorithmic point of view. The strong polynomial-time algorithms we design for the weighted case exhibit nice combinatorial properties. These efficient algorithms strengthen the theoretical equivalence between packing and covering triangles in multigraphs and that in weighted simple graphs. Regarding hypergraph theory, we generalize previous results on linear 3-uniform graphs [10] to the ones without the linearity requirement (see Section 2.1). In addition, we establish a new upper bound on the transversal number of connected linear 3-uniform hypergraphs (Theorem 2.10); the proof implies a faster 2-approximation algorithm for finding minimum triangle cover in simple graph G provided $\nu _{t}(G)/|{\mathscr {T}}_{G}|\ge 1/3$ (see Algorithm 2, Corollaries 2.11 and 3.10). Moreover, as an application of condition (ii) in Theorem 1.3, we investigate Tuza’s conjecture on the classical Erdős-Rényi random graph $\mathcal {G}(n,p)$, and prove that Pr[τ _t (G)/ν _t (G) ≤ 2] = 1 − o(1) provided $G\in \mathcal {G}(n,p)$ and $p> \sqrt {3}/2$ (Theorem 3.14).

The rest of paper is organized as follows. Section 2 proves theoretical and algorithmic results on 3-uniform hypergraphs concerning feedback sets and transversals, which are main technical tools for establishing new sufficient conditions for (weighted) Tuza’s conjecture in Section 3. Section 4 concludes the paper with extensions and future research directions.

2 Hypergraphs

This section develops hypergraph tools for studying Tuza’s conjecture. 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 a hypergraph $\mathcal {H}^{\prime }=(\mathcal {V}^{\prime },\mathcal {E}^{\prime })$ satisfies $\mathcal {V}^{\prime } \subseteq \mathcal {V}$ and $\mathcal {E}^{\prime } \subseteq \mathcal {E}$, we call $\mathcal {H}^{\prime }$ a subhypergraph of $\mathcal {H}$, and write $\mathcal {H}^{\prime }\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 {Z}_{>0}$ be a positive integer. A 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}$. A hypergraph $\mathcal {H}$ is linear if |e ∩ f|≤ 1 for any pair of distinct edges $e,f\in \mathcal {E}$.

A vertex-edge alternating sequence v₁e₁v₂⋯v _k e _k v_k+ 1 of $\mathcal {H}$ is called a path (of lengthk) between v₁ and v_k+ 1 if $v_{1}, v_{2},{\ldots }, v_{k + 1}\in \mathcal {V}$ are distinct, $e_{1}, e_{2},{\ldots }, e_{k}\in \mathcal {E}$ are distinct, and {v _i , v_i+ 1}⊆ e _i for each i ∈ [k] = {1,…,k}. For each i ∈ [k], edges e _i and e_i+ 1 are consecutive, where e_k+ 1 = e₁. We consider each vertex of $\mathcal {H}$ as a path of length 0. A 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 subhypergraph of $\mathcal {H}$ is called a component of $\mathcal {H}$. Obviously, $\mathcal {H}$ is connected if and only if it has only one component.

A vertex-edge alternating sequence $\mathcal {C}= v_{1}e_{1}v_{2}e_{2}{\cdots } v_{k}e_{k}v_{1}$, where k ≥ 2, is called a cycle (of length k) if $v_{1}, v_{2},{\ldots }, v_{k}\in \mathcal {V}$ are distinct, $e_{1}, e_{2},{\ldots }, e_{k}\in \mathcal {E}$ are distinct, and {v _i , v_i+ 1}⊆ e _i for each i ∈ [k], where v_k+ 1 = v₁. We consider the cycle $\mathcal {C}$ as a subhypergraph of $\mathcal {H}$ with vertex set ∪_i∈[k]e _i and edge set {e _i : i ∈ [k]}. We call vertices v₁, v₂,…,v _k join vertices of $\mathcal {C}$, and the other vertices non-join vertices of $\mathcal {C}$. For any $\mathcal {S}\subset \mathcal {V}$ (resp. $S\subset \mathcal {E}$), we write $\mathcal {H}\setminus \mathcal {S}$ for the subhypergraph 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 {S}$ and keeping all the 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}\uplus \mathcal {S}$, and as $\mathcal {H}\oplus \mathcal {S}$ if $\mathcal {S}\cap \mathcal {E}=\emptyset$. A connected hypergraph without any cycle is called a tree.

This section is divided into three subsections, discussing feedback sets of 3-uniform hypergraphs, weighted hypergraphs, and transversals (i.e., vertex sets covering all edges) of linear 3-uniform hypergraphs, respectively.

2.1 Feedback sets

Let $\mathcal {H}=(\mathcal {V},\mathcal {E})$ be a hypergraph. 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 quasi-FVS of $\mathcal {H}$ if it intersects every cycle of length at least 3 in $\mathcal {H}$. Let $\tau ^{{~}_{\mathcal {V}}}_{c}(\mathcal {H})$, $\tau _{c}^{{~}_{\mathcal {E}}}(\mathcal {H})$ and $\tau ^{{~}_{\mathcal {V}}}_{\circ }(\mathcal {H})$ denote, respectively, the minimum cardinalities of a FVS, a FES, and a quasi-FVS of $\mathcal {H}$. It is easy to see that $\tau ^{{~}_{\mathcal {V}}}_{\circ }(\mathcal {H})\le \tau ^{{~}_{\mathcal {V}}}_{c}(\mathcal {H})\leq \tau _{c}^{{~}_{\mathcal {E}}}(\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}$ (with $\mathcal {S}\subset \mathcal {V}$ or $\mathcal {S}\subset \mathcal {E}$), then $\mathcal {H}$ and $\mathcal {H}\setminus \mathcal {S}$ have the same set of quasi-FVS’s, and $\tau _{\circ }^{{~}_{\mathcal {V}}}(\mathcal {H})= \tau _{\circ }^{{~}_{\mathcal {V}}}(\mathcal {H}\setminus \mathcal {S})$. The following theorem is one of main contributions of this paper.

Theorem 2.1

Let $\mathcal {H}$ be a 3-uniform hypergraph. Then $\tau _{\circ }^{{~}_{\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 _{\circ }^{{~}_{\mathcal {V}}}(\mathcal {H})> |\mathcal {E}|/3$ such that $|\!|\mathcal {H}|\!|=|\mathcal {E}|$ is as small as possible. Obviously $|\mathcal {E}|\geq 3$. Without loss of generality, we can assume that $\mathcal {H}$ has no isolated vertices.

If there exists $e\in \mathcal {E}$ which does not belong to any cycle of $\mathcal {H}$ with length at least 3, then $\tau _{\circ }^{{~}_{\mathcal {V}}}(\mathcal {H})= \tau _{\circ }^{{~}_{\mathcal {V}}}(\mathcal {H}\setminus e)$. The minimality of $\mathcal {H}=(\mathcal {V},\mathcal {E})$ implies $\tau _{\circ }^{{~}_{\mathcal {V}}}(\mathcal {H}\setminus e)\leq (|\mathcal {E}|-1)/3$, giving $\tau _{\circ }^{{~}_{\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}$ with length at least 3.

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

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

  If $\mathcal {H}$ has a pair of distinct edges e = {t, u, v} and f sharing two common vertices u, v, then from (2) we see that u and v are incident with e and f only. In view of (1), considering a cycle of length at least 3 that goes through e, we deduce that this cycle goes through an edge $g\in \mathcal {E}-\{e,f\}$ which is incident with e at vertex t. See Fig. 1 for an illustration. Let $\mathcal {S}$ be a minimum quasi-FVS of $\mathcal {H}^{\prime }=\mathcal {H}\setminus \{e,f,g\}$. It follows from (2) that $\mathcal {H}\setminus t\subseteq \mathcal {H}\setminus \{e,g\}=\mathcal {H}^{\prime }\oplus f$, and in $\mathcal {H}\setminus \{e,g\}$, edge f intersects at most one other edge, which avoids u and v. Therefore f is not contained in any cycle in $\mathcal {H}\setminus \{e,g\}$. Thus $\mathcal {S}$ is a quasi-FVS of $\mathcal {H}\setminus \{e,g\}$, and hence a quasi-FVS of $\mathcal {H}\setminus t$. So $\{t\}\cup \mathcal {S}$ is a quasi-FVS of $\mathcal {H}$. We deduce that $|\mathcal {E}|/3<\tau _{\circ }^{{~}_{\mathcal {V}}}(\mathcal {H})\le |\{t\}\cup \mathcal {S}|\le 1+|\mathcal {S}|$. Therefore $\tau _{\circ }^{{~}_{\mathcal {V}}}(\mathcal {H}^{\prime })=|\mathcal {S}|>(|\mathcal {E}|-3)/3=|\!|\mathcal {H}^{\prime }|\!|/3$ shows a contradiction to the minimality of $\mathcal {H}$.

  Henceforth, we assume $\mathcal {H}$ is linear, and any cycle in $\mathcal {H}$ is of length at least 3. In any subhypergraph $\mathcal {H}^{\prime }$ of $\mathcal {H}$, all quasi-FVS are FVS, and $\tau _{\circ }^{{~}_{\mathcal {V}}}(\mathcal {H}^{\prime })=\tau _{c}^{{~}_{\mathcal {V}}}(\mathcal {H}^{\prime })$.

  Suppose that there exists $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₁ is contained in a cycle $\mathcal {C}= v_{1}e_{1}v_{2}e_{2}v_{3}{\cdots } e_{k}v_{1}$, where k ≥ 3. By (2), we have $d_{\mathcal {H}}(v_{i})= 2$ for all i ∈ [k]. In particular $d_{\mathcal {H}}(v_{1})=d_{\mathcal {H}}(v_{2})= 2>d_{\mathcal {H}}(v)$ implies v∉{v₁, v₂}, and in turn v₁, v₂, v ∈ e₁ enforces e₁ = {v₁, v, v₂}. Let $\mathcal {S}$ be a minimum FVS of $\mathcal {H}^{\prime }=\mathcal {H}\setminus \{e_{1},e_{2},e_{3}\}$. It follows from (2) that

  $$\mathcal{H}\setminus v_{3}\subseteq \mathcal{H}\setminus\{e_{2},e_{3}\}= \mathcal{H}^{\prime}\oplus e_{1},$$

  and in $\mathcal {H}^{\prime }\oplus e_{1}$, edge e₁ intersects at most one other edge, and therefore is not contained in any cycle. Thus $\mathcal {S}$ is a FVS of $\mathcal {H}^{\prime }\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}^{\prime })=|\mathcal {S}|>(|\mathcal {E}|-3)/3=|\!|\mathcal {H}^{\prime }|\!|/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_{1}e_{1}v_{2}e_{2}{\cdots } v_{k}e_{k}v_{1}$ be a shortest cycle in $\mathcal {H}$, where k ≥ 3. For each i ∈ [k], suppose that e _i = {v _i , u _i , v_i+ 1}, where v_k+ 1 = v₁.

  Because $\mathcal {C}$ is a shortest cycle, for each pair of distinct indices i, j ∈ [k], we have e _i ∩ e _j = ∅ if and only if e _i and e _j are not adjacent in $\mathcal {C}$, i.e., |i − j|∉{1,k − 1}. This fact along with the linearity of $\mathcal {H}$ says that v₁, v₂,…,v _k , u₁, u₂,…,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 ∈ [k]. We distinguish among three cases depending on the values of k (mod 3). In each case, we construct a proper subhypergraph $\mathcal {H}^{\prime }$ of $\mathcal {H}$ with $|\!|\mathcal {H}^{\prime }|\!|<|\!|\mathcal {H}|\!|$ and $\tau _{c}^{{~}_{\mathcal {V}}}(\mathcal {H}^{\prime })>|\!|\mathcal {H}^{\prime }|\!|/3$ which shows a contradiction to the minimality of $\mathcal {H}$.

Fig. 1

The case of nonlinearity

Case 1. k ≡ 0 (mod 3)

Let $\mathcal {S}$ be a minimum FVS of $\mathcal {H}^{\prime }=\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

$$\mathcal{H}\setminus \mathcal{V}_{*}\subseteq (\mathcal{H}\setminus\mathcal{E}_{c})\oplus \mathcal{E}_{*}= \mathcal{H}^{\prime}\oplus \mathcal{E}_{*},$$

and in $\mathcal {H}^{\prime }\oplus \mathcal {E}_{*}$, each edge in $\mathcal {E}_{*}$ intersects exactly one other edge, and therefore is not contained in any cycle. Thus $(\mathcal {H}^{\prime }\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}^{\prime })=|\mathcal {S}|>(|\mathcal {E}|-k)/3=|\!|\mathcal {H}^{\prime }|\!|/3$ shows a contradiction.

Case 2. k ≡ 1 (mod 3)

Consider the case where f₁≠f₃ or f₂≠f₄. Relabeling the vertices and edges if necessary, we may assume without loss of generality that f₁≠f₃. Let $\mathcal {S}$ be a minimum FVS of $\mathcal {H}^{\prime }=\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

$$\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}^{\prime}\oplus (\{e_{2},e_{4}\}\cup\mathcal{E}_{*}).$$

Note from (3) that in $\mathcal {H}^{\prime }\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}^{\prime }\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}^{\prime })=|\mathcal {S}|>(|\mathcal {E}|-k-2)/3=|\mathcal {H}^{\prime }|/3$, a contradiction.

Consider the case where f₁ = f₃ and f₂ = f₄. As u₁, u₂, u₃, u₄ are distinct and |f₁| = |f₂| = 3, we have f₁≠f₂. Observe that u₁e₁v₂e₂v₃e₃u₃f₃u₁ 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}\}$ consists of 6 distinct edges. Let $\mathcal {S}$ be a minimum FVS of $\mathcal {H}^{\prime }=\mathcal {H}\setminus (\mathcal {E}_{c}\cup \{f_{1},f_{2}\})$. It follows from (3) that

$$\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}^{\prime}\oplus\{e_{1},e_{3},f_{1}\}.$$

In $\mathcal {H}^{\prime }\oplus \{e_{1},e_{3},f_{1}\}$, both e₁ and e₃ intersect only one other edge, which is f₁, and any cycle through f₁ must contain e₁ or e₃. It follows that none of e₁, e₃, f₁ is contained in a cycle of $\mathcal {H}^{\prime }\oplus \{e_{1},e_{3},f_{1}\}$. Thus $(\mathcal {H}^{\prime }\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}|\leq 2+ |\mathcal {S}|$. In turn $\tau _{c}^{{~}_{\mathcal {V}}}(\mathcal {H}^{\prime })=|\mathcal {S}|>(|\mathcal {E}|-6)/3=|\!|\mathcal {H}^{\prime }|\!|/3$ shows a contradiction.

Case 3. k ≡ 2 (mod 3)

Let $\mathcal {S}$ be a minimum FVS of $\mathcal {H}^{\prime }=\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

$$\mathcal{H}\setminus(\{u_{1}\}\cup\mathcal{V}_{*})\subseteq (\mathcal{H}\setminus(\mathcal{E}_{c}\cup \{f_{1}\}))\oplus \mathcal{E}_{*}= \mathcal{H}^{\prime}\oplus\mathcal{E}_{*}$$

In $\mathcal {H}^{\prime }\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}^{\prime }\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}^{\prime })=|\mathcal {S}|>(|\mathcal {E}|-k-1)/3=|\!|\mathcal {H}^{\prime }|\!|/3$.

The combination of the above three cases completes the proof. □

Corollary 2.2

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

We remark that the upper bound $|\!|\mathcal {H}|\!|/3$ in Theorem 2.1 and Corollary 2.2 is best possible. See Fig. 2 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 linear 3-uniform $\mathcal {H}$ with $\tau _{c}^{{~}_{\mathcal {V}}}(\mathcal {H})= |\!|\mathcal {H}|\!|/3$) is at most three. It would be interesting to characterize all extremal hypergraphs for Corollary 2.2.

Fig. 2

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

The proof of Theorem 2.1 actually gives a recursive combinatorial algorithm for finding in polynomial time a quasi-FVS (resp. FVS) of size at most $|\!|\mathcal {H}|\!|/3$ on a 3-uniform (resp. 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. Any cycle in Step 9 or Step 11 can be found in $O(|\mathcal {E}|^{2})$ time.² Thus Algorithm 1 runs in $O(|\mathcal {E}|^{3})$ time.

Corollary 2.3

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

The goal of the next two lemmas is to establish an upper bound on the size of any minimal FES in a 3-uniform hypergraph $\mathcal {H}=(\mathcal {V},\mathcal {E})$. Since $\tau _{c}^{{~}_{\mathcal {V}}}(\mathcal {H})\leq \tau _{c}^{{~}_{\mathcal {E}}}(\mathcal {H})$, it follows that both $\tau _{c}^{{~}_{\mathcal {V}}}(\mathcal {H})$ and $\tau _{c}^{{~}_{\mathcal {E}}}(\mathcal {H})$ are bounded above by this bound.

Lemma 2.4

If $\mathcal {H}=(\mathcal {V},\mathcal {E})$ is a connected 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 3-uniform hypergraph with fewer edges 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 ∈ [3], hypergraph $\mathcal {H}_{i}$ with $|\mathcal {E}_{i}|<|\mathcal {E}|$ is connected, 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$. □

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 if the edge is redundant. The redundancy test can be implemented using Depth First Search.

Lemma 2.5

Let $\mathcal {H}=(\mathcal {V},\mathcal {E})$ be a 3-uniform hypergraph with p components. If$\mathcal {F}$ is a minimal FES of $\mathcal {H}$, then $|\mathcal {F}|\leq 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,…,k. It follows from Lemma 2.4 that $|\mathcal {V}_{i}|= 2|\mathcal {E}_{i}|+ 1$ for each i ∈ [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\leq |\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},{{\ldots }},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. □

2.2 Vertex-weighted hypergraphs

As will be seen later, we will convert our problem of finding triangle covering and packing numbers to the problem of weighted vertex covering and packing on an acyclic 3-uniform hypergraph. The latter problem has been known to be solvable in strongly polynomial time, for which we recall in this subsection some related results on hypergraph theory and integer programming.

Given a hypergraph $\mathcal {H}=(\mathcal {V},\mathcal {E})$ with n vertices and m edges, and a weight function $\mathbf {w}\in \mathbb {Z}_{>0}^{\mathcal {V}}$, the weight (also referred to as weighted cardinality) of any subset $\mathcal {S}$ of $\mathcal {V}$ and that of any subset $\mathcal {F}$ of $\mathcal {E}$ are defined as

$$|\mathcal{S}|_{w}=\sum\limits_{s\in \mathcal{S}}w(s) \text{\, and\,} |\mathcal{F}|_{w}=\sum\limits_{F\in \mathcal{F}}\prod\limits_{s\in F}w(s),$$

respectively. A transversal of $\mathcal {H}$ is a vertex subset of $\mathcal {V}$ that intersects each edge in $\mathcal {E}$. A w-matching of $\mathcal {H}$ is a collection of edges in $\mathcal {H}$ (repetition allowed) such that each vertex $v\in \mathcal {V}$ appears in at most w(v) members of the collection. Let $\tau (\mathcal {H},\mathbf {w})$ and $\nu (\mathcal {H},\mathbf {w})$ denote the minimum weight of a transversal and maximum cardinality of a w-matching of $\mathcal {H}$, respectively. It is well known that $\tau (\mathcal {H},\mathbf {w})\ge \nu (\mathcal {H},\mathbf {w})$.

Let $M_{\mathcal {H}}$ be the $\mathcal {V}\times \mathcal {E}$ incidence matrix. From $M_{\mathcal {H}}$, we can construct a bipartite graph $G_{\mathcal {H}}$ with bipartition $\mathcal {V},\mathcal {E}$ such that there is an edge of $G_{\mathcal {H}}$ between $v\in \mathcal {V}$ and $e\in \mathcal {E}$ if and only if v ∈ e in $\mathcal {H}$. Suppose that $\mathcal {H}$ is acyclic. It is easy to see that $G_{\mathcal {H}}$ is acyclic. Thus $M=M_{\mathcal {H}}$ falls within the class of restricted totally unimodular (RTUM) matrices defined by Yannakakis [11]. As the name indicates, RTUM matrices are all totally unimodular. Hence the total unimodularity and LP duality give the well-known result [12] that

$$\tau(\mathcal{H},\mathbf{w})=\min\{\mathbf{w}^{T}\mathbf{x}:M^{T}\mathbf{x}\ge\mathbf{1},x\geq 0\}\!=\max\{\mathbf{1}^{T}\mathbf y:M\mathbf y\le\mathbf{w},y\geq 0\}=\nu(\mathcal{H},\mathbf{w}).$$

Moreover, since M is RTUM, both a minimum weighted transversal and a maximum weighted matching of $\mathcal {H}$ can be found in O(n(m + n log n)log n) time using Yanakakis’s combinatorial algorithm [11] based on the current best combinatorial algorithms for the b-matching problem and the maximum weighted independent set problem on a bipartite multigraph with n vertices and m edges, where the bipartite b-matching problem can be solved with the minimum-cost flow algorithm in O(n log n(m + n log n)) time (see Section 21.5 and page 356 of [13]) and the maximum weighted independent set problem can be solved with maximum flow algorithm in O(nm log n) time (See pages 300-301 of [11]).

Theorem 2.6 ([11, 12])

Let $\mathcal {H}=(\mathcal {V},\mathcal {E})$be a hypergraph with n non-isolated vertices and m edges, and$\mathbf {w}\in \mathbb {Z}_{>0}^{\mathcal {V}}$. If $\mathcal {H}$ has no cycle, then $\tau (\mathcal {H},\mathbf {w})=\nu (\mathcal {H},\mathbf {w})$, and a minimum weighted transversal and a maximumw-matching of $(\mathcal {H},\mathbf {w})$ can be found in O(n(m + n log n)log n) time.

In the case of unit weight (i.e., the unweighted case), 1-matching of $\mathcal {H}$ is often referred to as a matching of $\mathcal {H}$, which is a nonempty set of pairwise disjoint edges in $\mathcal {H}$. As usual, $\tau (\mathcal {H},\mathbf {1})$ and $\tau (\mathcal {H},\mathbf {1})$ are abbreviated as $\tau (\mathcal {H})$ and $\nu (\mathcal {H})$, respectively; the symbol |⋅|₁ is simply the traditional |⋅| representing cardinality. Clearly $\tau (\mathcal {H})\ge \tau ^{{~}_{\mathcal {V}}}_{c}(\mathcal {H})$.

2.3 Transversals

In this subsection, we will upper bound $\tau (\mathcal {H})$ for connected linear 3-uniform hypergraph $\mathcal {H}$ by $(2|\!|\mathcal {H}|\!|+ 1)/3$. To this end, we first study some properties of cycles and components in these hypergraphs. Then we establish the upper bound in Theorem 2.10.

A cycle in a hypergraph is minimal if every pair of nonconsecutive edges of the cycle is vertex-disjoint. A pair of (minimal) cycles are called intersecting if these two cycles have at least one vertex in common. A partition of a set into two parts is called nontrivial if neither of the two parts is empty.

Lemma 2.7

Let $\mathcal {C}=(\mathcal {V},\mathcal {E})$ be a linear 3-uniform hypergraph that is a cycle. If$\mathcal {C}$ is not minimal, then there exists a pair of intersecting cycles$\mathcal {C}_{i}=(\mathcal {V}_{i},\mathcal {E}_{i})$,i = 1,2, in $\mathcal {C}$ such that $|\mathcal {V}_{1}|< |\mathcal {V}|$,$|\mathcal {V}_{2}|< |\mathcal {V}|$,$\mathcal {E}= \mathcal {E}_{1} \cup \mathcal {E}_{2}$,$\mathcal {E}_{1} \cap \mathcal {E}_{2}\neq \emptyset$, and $|\mathcal {E}_{1}|+|\mathcal {E}_{2}|\le |\mathcal {E}|+ 2$.

Proof

We may order the vertices and edges of the cycle $\mathcal {C}$ so that $\mathcal {C}= v_{1}e_{1}v_{2}e_{2}{\cdots } v_{k}e_{k}v_{1}$ has two nonconsecutive edges e₁ and e _i that have a vertex v in common, where 3 ≤ i ≤ k − 1. Recall that v₁, v₂,…,v _k (resp. e₁, e₂,…,e _k ) are all distinct. If v∉{v₁, v₂,…,v _k }, then $\mathcal {C}$ properly contains cycles $\mathcal {C}_{1}=ve_{1}v_{2}e_{2}{\cdots } v_{i}v$ with length $i<k=|\mathcal {V}|$ and $\mathcal {C}_{2}=ve_{i}v_{i + 1}{\cdots } v_{k}e_{k}v_{1}e_{1}v$ with length $k-i + 2<k=|\mathcal {V}|$. It is clear that $\mathcal {C}_{1}$ and $\mathcal {C}_{2}$ satisfy the conclusion of the lemma. It remains to consider the case where either e₁ or e _i consists of three vertices from {v₁, v₂,…,v _k }. By symmetry, we may assume e₁ = {v₁, v₂, v _j } for some j ∈ [3,k]. The linearity of $\mathcal {C}$ enforces 4 ≤ j ≤ k − 1, giving $\mathcal {C}_{1}=v_{j}e_{1}v_{2}e_{2}{\cdots } e_{j-1}v_{j}$ and $\mathcal {C}_{2}=v_{j}e_{j}v_{j + 1}{\cdots } v_{k}v_{1}e_{1}v_{j}$ as desired. □

Corollary 2.8

A linear 3-uniform hypergraph $\mathcal {H}$ has a pair of intersecting cycles if and only if $\mathcal {H}$ has a pair of intersecting minimal cycles.

Proof

Take $\mathcal {C}=(\mathcal {V},\mathcal {E})$ and $\mathcal {C}^{\prime }=(\mathcal {V}^{\prime },\mathcal {E}^{\prime })$ to be a pair of intersecting cycles in $\mathcal {H}$ such that $|\mathcal {E}|+|\mathcal {E}^{\prime }|$ is as small as possible. If one of $\mathcal {C}$ and $\mathcal {C}^{\prime }$, say $\mathcal {C}$, is not minimal, then by Lemma 2.7, $\mathcal {C}$ and hence $\mathcal {H}$ contain a pair of intersecting cycles $\mathcal {C}_{i}=(\mathcal {V}_{i},\mathcal {E}_{i})$, i = 1,2, with $|\mathcal {E}_{1}|+|\mathcal {E}_{2}|\le |\mathcal {E}|+ 2<|\mathcal {E}|+|\mathcal {E}^{\prime }|$, which gives a contradiction to the minimality of $|\mathcal {E}|+|\mathcal {E}^{\prime }|$. □

Lemma 2.9

Let $\mathcal {H}=(\mathcal {V},\mathcal {E})$ be a connected linear 3-uniform hypergraph. If $\mathcal {H}$ has a pair of intersecting cycles, then there exists a vertex $v\in \mathcal {V}$ such that $\mathcal {H}\setminus v$ has at most $2d_{\mathcal {H}}(v)-2$ components.

Proof

By Corollary 2.8, there exists a pair of intersecting minimal cycles $\mathcal {C}_{1}=v_{1}e_{1}v_{2}e_{2}{\cdots } v_{k}e_{k}v_{1}$ and $\mathcal {C}_{2}=u_{1}f_{1}u_{2}f_{2}{\cdots } u_{\ell } f_{\ell } u_{1}$ in $\mathcal {H}$. Since $\mathcal {H}$ is 3-uniform and linear, for any vertex v of $\mathcal {H}$, we observe that v has $2d_{\mathcal {H}}(v)$ neighbors in $\mathcal {H}$. The connectivity of $\mathcal {H}$ implies each component of $\mathcal {H}\setminus v$ has to contain at least one of these $2d_{\mathcal {H}}(v)$ neighbors.

If $\mathcal {C}_{1}$ and $\mathcal {C}_{2}$ do not have any common edge, let v be an arbitrarily taken common vertex of $\mathcal {C}_{1}$ and $\mathcal {C}_{2}$. For i = 1,2, no matter v is a join vertex of $\mathcal {C}_{i}$ or not, v is adjacent to exactly two join vertices of $\mathcal {C}_{i}$, which we denote as a _i , b _i . See Fig. 3 for an illustration. Since $\mathcal {C}_{i}$ is minimal, v’s neighbors a _i and b _i belong to the same component of $\mathcal {H}\setminus v$. Hence $\mathcal {H}\setminus v$ has at most $2d_{\mathcal {H}}(v)-2$ components.

Fig. 3

Two neighbors a _i , b _i (i = 1,2) of v belong to the same component of $\mathcal {H}\setminus v$

If $\mathcal {C}_{1}$ and $\mathcal {C}_{2}$ have some edge(s) in common, then, as $\mathcal {C}_{1}$ and $\mathcal {C}_{2}$ are distinct, we may assume $e_{1}\in \mathcal {C}_{2}$ and $e_{2}\not \in \mathcal {C}_{2}$ as illustrated in Fig. 4. In case of v₁, v₂ both being join vertices of $\mathcal {C}_{2}$ (Fig. 4a), we have v = v₂ adjacent to exactly two join vertices of $\mathcal {C}_{2}$ – one is v₁ and the other written as u is not v₃. So v₁, v₃, u are three distinct neighbors of v which are contained in the same component of $\mathcal {H}\setminus v$, and we are done. In case of only one of v₁ and v₂ being join vertex of $\mathcal {C}_{2}$ (Fig. 4b), let v be the join vertex of $\mathcal {C}_{2}$ contained in e₁ ∖{v₁, v₂} and u be v’s neighbor which is a join vertex of $\mathcal {C}_{2}$ other than v₁ and v₂. Now we see that v₁, v₂, u are three distinct neighbors of v that are contained in the same component of $\mathcal {H}\setminus v$. In either case, we reach the conclusion that $\mathcal {H}\setminus v$ has at most $2d_{\mathcal {H}}(v)-2$ components. □

Fig. 4

Three neighbors u, v₁, v _i (i = 2 or 3) of v belong to the same component of $\mathcal {H}\setminus v$

Theorem 2.10

Let $\mathcal {H}$ be a connected linear 3-uniform hypergraph. Then $\tau (\mathcal {H})\!\leq \frac {2|\!|\mathcal {H}|\!|+ 1}{3}$ .

Proof

By contradiction, we take a counterexample $\mathcal {H}=(\mathcal {V},\mathcal {E})$ with $\tau (\mathcal {H})> \frac {2|\!|\mathcal {H}|\!|+ 1}{3}$ such that $|\!|\mathcal {H}|\!|$ is minimum.

If $\mathcal {H}$ is acyclic, then $|\mathcal {V}|= 2|\!|\mathcal {H}|\!|+ 1$ by Lemma 2.4 and $\tau (\mathcal {H})=\nu (\mathcal {H})$ by Theorem 2.6, implying a contradiction $\frac {2|\!|\mathcal {H}|\!|+ 1}{3}< \tau (\mathcal {H})=\nu (\mathcal {H})\leq \frac {|\mathcal {V}|}{3}=\frac {2|\!|\mathcal {H}|\!|+ 1}{3}$. Thus we have

• (1) $\mathcal {H}=(\mathcal {V},\mathcal {E})$ is not acyclic.

Suppose that there exists $v\in \mathcal {V}$ such that $\mathcal {H}\setminus v$ consists of k components $\mathcal {H}_{1}, \ldots ,\mathcal {H}_{k}$, where $k\le 2d_{\mathcal {H}}(v)-2$. The minimality of $|\!|\mathcal {H}|\!|$ implies $\tau (\mathcal {H}_{i})\le \frac {2|\!|\mathcal {H}_{i}|\!|+ 1}3$ for all i = 1,…,k. It follows that

$$\tau(\mathcal{H})\!\le 1+\tau(\mathcal{H}\setminus v)=\! 1+\sum\limits_{i = 1}^{k}\tau(\mathcal{H}_{i})\!\leq1+ \sum\limits_{i = 1}^{k}\!\frac{2|\!|\mathcal{H}_{i}|\!|+ 1}{3}\!=\frac{2[|\!|\mathcal{H}|\!|-d_{\mathcal{H}}(v)]+k}{3}+ 1,$$

which along with $k\le 2d_{\mathcal {H}}(v)-2$ gives $\tau (\mathcal {H}) \leq \frac {2|\!|\mathcal {H}|\!|+ 1}{3}$, a contradiction. Therefore for each vertex $v\in \mathcal {V}$, hypergraph $\mathcal {H}\setminus v$ has at least $2d_{\mathcal {H}}(v)-1$ components. It follows from Lemma 2.9 that $\mathcal {H}$ does not contain any pair of interesting cycles. In turn by Lemma 2.7 we see that all cycles of $\mathcal {H}$ are minimal, and they are connected by trees induced by edges of $\mathcal {H}$ not in any cycle. Let $\mathfrak {C}$ denote the set of cycles in $\mathcal {H}$, and $\mathfrak {T}$ denote the set of components (maximal subtrees) of the hypergraph induced the edges of $\mathcal {E}$ not in any cycle of $\mathcal {H}$. We associate $\mathcal {H}$ with a graph G on vertex set $\mathfrak {C}\cup \mathfrak {T}$ in which vertex $\mathcal {C}\in \mathfrak {C}$ and vertex $\mathcal {T}\in \mathfrak {T}$ are joined by an edge if and only if in $\mathcal {H}$ cycle $\mathcal {C}$ and tree $\mathcal {T}$ have some vertex in common. See Fig. 5 for an illustration.

Fig. 5

Hypergraph $\mathcal {H}$ and its associated graph G, where $\mathfrak {C}=\{\mathcal {C}_{1},\mathcal {C}_{2},\mathcal {C}_{3}\}$ and $\mathfrak {T}=\{\mathcal {T}_{1},\mathcal {T}_{2},\mathcal {T}_{3},\mathcal {T}_{4},\mathcal {T}_{5}\}$

Since all cycles of $\mathcal {H}$ are vertex-disjoint, it is not hard to see that G is a tree. If $\mathcal {H}$ is simply a cycle, then $\tau (\mathcal {H})=\left \lceil \frac {|\!|\mathcal {H}|\!|}2\right \rceil$, which shows a contradiction to $\tau (\mathcal {H})> \frac {2|\!|\mathcal {H}|\!|+ 1}{3}$. Hence

• (2) G is a tree of at least two vertices, and it is a bipartite graph with bipartition $(\mathfrak {C},\mathfrak {T})$.

Consider any nontrivial partition $(\mathcal {E}^{\prime }_{1},\mathcal {E}^{\prime }_{2})$ of $\mathcal {E}$. For i = 1,2, let $\mathcal {H}^{\prime }_{i}$ denote the subhypergraph of $\mathcal {H}$ induced by $\mathcal {E}^{\prime }_{i}$. If $\mathcal {H}^{\prime }_{1}$ and $\mathcal {H}^{\prime }_{2}$ are connected, then the minimality of $|\!|\mathcal {H}|\!|$ implies $\tau (\mathcal {H}^{\prime }_{i})\le \frac {2|\!|\mathcal {H}^{\prime }_{i}|\!|+ 1}{3}$, i = 1,2. Since the union of transversals of $\mathcal {H}^{\prime }_{1}$ and $\mathcal {H}^{\prime }_{2}$ must be a transversal of $\mathcal {H}$, we have $\frac {2|\!|\mathcal {H}|\!|+ 1}{3}< \tau (\mathcal {H})\leq \tau (\mathcal {H}^{\prime }_{1})+\tau (\mathcal {H}^{\prime }_{2})\leq \frac {2|\!|\mathcal {H}^{\prime }_{1}|\!|+ 1}{3}+\frac {2|\!|\mathcal {H}^{\prime }_{2}|\!|+ 1}{3}=\frac {2|\!|\mathcal {H}|\!|+ 2}{3}$, which provides the following important property:

• (3) If $\mathcal {H}^{\prime }_{1}$ and $\mathcal {H}^{\prime }_{2}$ are both connected, then $\tau (\mathcal {H}^{\prime }_{i})= \frac {2|\!|\mathcal {H}^{\prime }_{i}|\!|+ 1}{3}$ for i = 1,2.

Recalling (2), we consider a leaf of G, which is a minimal cycle in $\mathfrak {C}$ or a tree in $\mathfrak {T}$. We denote it as $\mathcal {H}_{1}=(\mathcal {V}_{1},\mathcal {E}_{1})$. As G has at least two vertices, $\mathcal {E}_{2}=\mathcal {E}-\mathcal {E}_{1}$ is nonempty, and it induces a hypergraph $\mathcal {H}_{2}=(\mathcal {V}_{2},\mathcal {E}_{2})$. Because $\mathcal {H}_{1}$ is a leaf of G, both $\mathcal {H}_{1}$ and $\mathcal {H}_{2}$ are connected. Thus (3) guarantees that

• (4) $\tau (\mathcal {H}_{i})= \frac {2|\!|\mathcal {H}_{i}|\!|+ 1}{3}=\frac {2| \mathcal {E}_{i} |+ 1}{3}$ for i = 1,2.

Note that $\mathcal {H}_{1}\in \mathfrak {T}$ for otherwise $\mathcal {H}_{1}\in \mathfrak {C}$ would be a cycle for which we have $\tau (\mathcal {H}_{1})\leq \left \lceil \frac {|\!|\mathcal {H}_{1}|\!|}{2}\right \rceil <\frac {2|\!|\mathcal {H}_{1}|\!|+ 1}{3}$. In G, the leaf $\mathcal {H}_{1}\in \mathfrak {T}$ is adjacent to a unique neighbor $\mathcal {C}$, which belongs to $\mathfrak {C}$. By the linearity of $\mathcal {H}$, it is easy to see that tree $\mathcal {H}_{1}$ and cycle $\mathcal {C}$ intersect at exactly one vertex of $\mathcal {V}$, which we denote as v.

Let $u_{1}\in \mathcal {V}_{1}$ be a vertex in $\mathcal {H}_{1}$ which is at the maximum distance from v. If u₁ is not adjacent to v in $\mathcal {H}_{1}$, the unique path between u₁ and v may be written as u₁e₁u₂e₂u₃⋯v (see Fig. 6a for an illustration). Suppose e₁ = {u₁, v₁, u₂} and e₂ = {u₂, v₂, u₃}. Because u₁ is the farthest vertex from v in $\mathcal {H}_{1}$, it must be the case that $d_{\mathcal {H}}(u_{1})=d_{\mathcal {H}}(v_{1})= 1$. Let $\mathcal {E}_{1}^{\prime }$ be the set of edges in $\mathcal {H}$ incident with u₂ or v₂. The choice of u₁ implies that all edges in $\mathcal {E}_{1}^{\prime }-\{e_{2}\}$ are pendant. It follows that $\mathcal {E}_{1}^{\prime }$ and $\mathcal {E}_{2}^{\prime }=\mathcal {E}-\mathcal {E}_{1}^{\prime }$ induce connected hypergraphs $\mathcal {H}_{1}^{\prime }$ and $\mathcal {H}_{2}^{\prime }$, respectively. By (3), we have $\tau (\mathcal {H}^{\prime }_{1})= \frac {2|\mathcal {E}^{\prime }_{1}|+ 1}{3}$. Since $\tau (\mathcal {H}^{\prime }_{i})$ is an integer, and $\mathcal {E}^{\prime }_{1}$ contains e₁ and e₂ which are distinct, we deduce that $\tau (\mathcal {H}^{\prime }_{1})\ge 3$, which contradicts the fact that {u₂, v₂} is a transversal of $\mathcal {H}^{\prime }_{1}$. The contradiction implies that u₁ is adjacent to v in $\mathcal {H}$. Furthermore, the choice of u₁ enforces that all vertices in $\mathcal {V}_{1}-\{v\}$ are adjacent to v. Hence, {v} is a transversal of $\mathcal {H}_{1}$, which along with (4) enforces the following:

• (5) $\mathcal {E}_{1}$ consists of only one edge e₁.

  Fig. 6

  

  $\mathcal {H}_{1}$ and its neighboring structures

Note that v is incident with one or two edges in $\mathcal {C}$. We take e to be one of them. See Fig. 6b and c for illustrations. Let hypergraphs $\mathcal {H}^{\prime }_{1}$ and $\mathcal {H}^{\prime }_{2}$ be induced by $\mathcal {E}^{\prime }_{1}=\{e,e_{1}\}$ and $\mathcal {E}-\mathcal {E}^{\prime }_{1}$ respectively. Clearly,

• (6) $\mathcal {H}^{\prime }_{1}$ is connected, and {v} is a transversal of $\mathcal {H}^{\prime }_{1}$.

Note that $\frac {2|\!|\mathcal {H}^{\prime }_{1}|\!|+ 1}{3}=\frac {2\times 2 + 1}3$ is not an integer. The combination of (3) and (6) implies that $\mathcal {H}^{\prime }_{2}$ is not connected. If v is a non-join vertex of $\mathcal {C}$ (as depicted in Fig. 6b), then it can be easily seen from (5) that $\mathcal {H}^{\prime }_{2}$ is connected. The contradiction reduces us to the case where v is a join-vertex of $\mathcal {C}$, as depicted in Fig. 6c. Observe from (5) that $\mathcal {H}^{\prime }_{2}$ can have at most two components. So $\mathcal {H}^{\prime }_{2}$ consists of exactly two components, written as $\mathcal {H}_{3}$ and $\mathcal {H}_{4}$. The minimality of $\mathcal {H}$ guarantees $\tau (\mathcal {H}_{i})\leq \frac {2|\!|\mathcal {H}_{i}|\!|+ 1}{3}$ for i = 3,4. Since the union of minimum transversals of $\mathcal {H}^{\prime }_{1}$, $\mathcal {H}_{3}$, $\mathcal {H}_{4}$ is a transversal of $\mathcal {H}$, and $\tau (\mathcal {H}^{\prime }_{1})= 1$ by (6), we reach a contradiction $\frac {2|\!|\mathcal {H}|\!|+ 1}{3}<\tau (\mathcal {H})\leq \tau (\mathcal {H}^{\prime }_{1})+\tau (\mathcal {H}_{3})+\tau (\mathcal {H}_{4})\leq 1+\frac {2|\!|\mathcal {H}_{3}|\!|+ 1}{3}+\frac {2|\!|\mathcal {H}_{4}|\!|+ 1}{3} =\frac {2|\!|\mathcal {H}|\!|+ 1}{3}$, where the last equation is implied by $|\!|\mathcal {H}_{3}|\!|+|\!|\mathcal {H}_{4}|\!|=|\!|\mathcal {H}_{2}^{\prime }|\!|=|\!|\mathcal {H}|\!|-|\!|\mathcal {H}_{1}^{\prime }|\!|=|\!|\mathcal {H}|\!|-2$. This completes the proof of the theorem. □

The proof of Theorem 2.10 actually gives a recursive combinatorial algorithm for finding in polynomial time a transversal of size at most $(2|\!|\mathcal {H}|\!|+ 1)/{3}$ in a connected linear 3-uniform hypergraph $\mathcal {H}=(\mathcal {V},\mathcal {E})$. For any nonempty $\mathcal {F}\subseteq \mathcal {E}$, we use $\mathcal {H}[\mathcal {F}]$ to denote the subhypergraph of $\mathcal {H}$ induced by $\mathcal {F}$.

By Theorem 2.6, the total running of for all iterations of Step 2 is $O(|\mathcal {V}|(|\mathcal {E}|+|\mathcal {V}|\log |\mathcal {V}|)\log |\mathcal {V}|)$. Steps 3 – 4 are implemented at most $|\mathcal {V}|$ times, each taking $O(|\mathcal {V}|\cdot |\mathcal {E}|)$ time. Steps 5 – 21 are implemented at most $|\mathcal {V}|$ times, each taking $O(|\mathcal {E}|)$ time. Thus Algorithm 2 runs in $O(|\mathcal {V}|(|\mathcal {E}|+|\mathcal {V}|\log |\mathcal {V}|)\log |\mathcal {V}|)$ time.

Corollary 2.11

Given any connected linear 3-uniform hypergraph $\mathcal {H}$ on n vertices and m edges, Algorithm 2 finds in O(n(m + n log n)log n) time a transversal of $\mathcal {H}$ with size at most (2m + 1)/3.

3 Triangle Packing and Covering

This section establishes several new sufficient conditions for Conjectures 1.1 and 1.2 as well as their algorithmic implications on finding minimum triangle covers. Section 3.1 relates weighted triangle packing and covering in graphs to weighted matching and transversal in triangle hypergraphs, and studies the strong polynomial-time computation of weighted transversals in linear triangle hypergraphs. Section 3.2 deals with graphs of large weighted triangle packing numbers. Section 3.3 investigates irreducible graphs with large weighted numbers of edges.

3.1 Triangle hypergraphs

To each graph G = (V, E), we associate a hypergraph $\mathcal {H}_{G}=(E,{\mathscr {T}}_{G})$, referred to as triangle hypergraph of G, such that the vertices and edges of $\mathcal {H}_{G}$ are the edges and triangles of G, respectively. It is easy to see that $\mathcal {H}_{G}$ is 3-uniform, $\nu (\mathcal {H}_{G})=\nu _{t}(G)$ and $\tau (\mathcal {H}_{G})=\tau _{t}(G)$. Note that the number of non-isolated vertices of $\mathcal {H}_{G}$ is upper bounded by $3|\!|\mathcal {H}_{G}|\!|= 3|{\mathscr {T}}_{G}|$, and $|E|\le 3|{\mathscr {T}}_{G}|$ if G is irreducible, i.e., $\cup _{T\in {\mathscr {T}}_{G}}E(T)=E$.

In order to deal with polynomial-time computability of the weighted triangle covering of weighted graph (G, w) with G = (V, E) being simple and $\mathbf {w}\in \mathbb {Z}_{>0}^{E}$, we do not work directly on the graph G _w obtained from G by replacing each edge e ∈ E with a set E _e of w(e) edges of the same ends as e. Before proceeding to discuss the algorithmic details, we make some easy but important observations which will be used implicitly throughout the rest of this paper.

Observation 3.1

The following hold for every edge-weighted graph (G, w).

• (i) The weighted triangle covering number $\tau _{t}(G,\mathbf {w})=\tau (\mathcal {H}_{G},\mathbf {w})$ equals $\tau _{t}(G_{w})=\tau (\mathcal {H}_{G_{w}})$;

• (ii) The weighted triangle packing number $\nu _{t}(G,\mathbf {w})=\nu (\mathcal {H}_{G},\mathbf {w})$ equals $\nu _{t}(G_{w})=\nu (\mathcal {H}_{G_{w}})$;

• (iii) The weighted number of triangles $|{\mathscr {T}}_{G}|_{w}={\sum }_{\{x,y,z\}\in {\mathscr {T}}_{G}}w(x)w(y)w(z)$ equals $|{\mathscr {T}}_{G_{w}}|$;

• (iv) The weighted number of edges $|E|_{w}={\sum }_{e\in E(G)}w(e)$ equals |E(G _w )|.

In our algorithms for finding a FVS in a vertex-weighted triangle hypergraph, at the very beginning we treat each E _e as a single e by introducing to e a weighted degree in hypergraph $\mathcal {H}=(\mathcal {V},\mathcal {E})$, where $\mathcal {V}\subseteq E$ and $\mathcal {E}\subseteq {\mathscr {T}}_{G}$. The weighted degree$d_{\mathcal {H}}^{w}(e)$ of $e\in \mathcal {V}$ in $\mathcal {H}$ is defined as

$$d_{\mathcal{H}}^{w}(e)=\sum\limits_{f,g:\{e,f,g\}\in\mathcal{E}}w(f)w(g),$$

which can be computed in O(|V|²) time. It is worth noting that $d_{\mathcal {H}_{G}}^{w}(e)$ equals $d_{\mathcal {H}_{G_{w}}}(f)$ for all f ∈ E _e . A crucial observation on Algorithm 1 is the following.

Observation 3.2

There exists an implementation of Algorithm 1 with input $\mathcal {H}_{G_{w}}$ such that if an edge s ∈ E is found and removed from the hypergraph in Step 2 (resp. Step 4), then all edges in E _s are removed one by one in Step 2 (resp. Step 4) of the following recursions.

The correctness of the observation is guaranteed by the fact that all f ∈ E _e have the same degree in $\mathcal {H}_{G_{w}}$ and in each subhypergraph of $\mathcal {H}_{G_{w}}$ produced by Algorithm 1, and the deletion of an f ∈ E _e does not change the degree of other members of E _e . By virtue of the observation, we can compute a FVS in a vertex-weighted linear 3-uniform hypergraph as in Algorithm 3.

Observation 3.3

After recursions at Steps 2-5 of Algorithm 3, we obtain a hypergraph $\mathcal {H}=(\mathcal {V},\mathcal {E})$ with w(e) ∈{1,2} for all $e\in \mathcal {V}$.

Proof

To see it, suppose the contrary: w(e) ≥ 3 for some $e\in \mathcal {V}$. Let $\{e,f,g\}\in \mathcal {E}$ be a triangle containing e. Then $d_{\mathcal {H}}^{w}(f)\ge w(e)\ge 3$ says that f should have been removed at Step 5. □

Now let us consider the implementation of Algorithm 1 with input $\mathcal {H}_{G_{w}}$ stated in Observation 3.2. The hypergraph its Step 6 faces corresponds to the hypergraph $\mathcal {H}$ reached by Step 6 of Algorithm 3. By Observation 3.3, the former hypergraph is exactly the hypergraph $\mathcal {H}^{\prime }$ constructed at Step 7 of Algorithm 3. (Note that each pair of x, x^′ in $\mathcal {H}^{\prime }$ simulates a pair of parallel edges in G _w .) Hence Step 8 of Algorithm 3 simply conducts the computations done by Steps 6 – 21 of Algorithm 1. Furthermore, from the construction of $\mathcal {H}^{\prime }$, it is straightforward that for any $x\in \mathcal X$, if $|\mathcal {S}\cap \{x,x^{\prime }\}|= 1$ then $\mathcal {S}- \{x,x^{\prime }\}$ is a quasi-FVS of $\mathcal {H}^{\prime }$. It follows that the setting in Step 9 of Algorithm 3 does provide a FVS of the linear 3-uniform hypergraph $\mathcal {H}$.

Theorem 3.4

Given any linear triangle hypergraph $\mathcal {H}=(\mathcal {V},\mathcal {E})$ and any $\mathbf {w}\in \mathbb {Z}_{>0}^{\mathcal {V}}$ , Algorithm 3 finds in $O(|\!|\mathcal {H}|\!|^{3})$ time a FVS $\mathcal {S}$ of $\mathcal {H}$ whose weight $|\mathcal {S}|_{w}={\sum }_{s\in \mathcal {S}}w(s)$ is at most $\frac {1}{3}|\mathcal {E}|_{w}=\frac {1}{3}{\sum }_{\{x,y,z\}\in \mathcal {E}}w(x)w(y)w(z)$ .

Proof

Suppose that a simple graph G satisfies $\mathcal {H}=\mathcal {H}_{G}$ and $\mathcal {S}_{w}$ is the output of Algorithm 1 with input G _w . It is not hard to check that ${\sum }_{s\in \mathcal {S}}w(s)=|\mathcal {S}_{w}|$ and ${\sum }_{\{x,y,z\}\in \mathcal {E}}w(x)w(y)w(z)=|\!|\mathcal {H}_{G_{w}}|\!|$. The result is instant from Corollary 2.3. □

In case of finding a minimal FES in $\mathcal {H}_{G_{w}}$, we remove redundant triangles (edges of $\mathcal {H}_{G_{w}}$) from any given FES. Using a similar idea to Observation 3.2, once a triangle is removed we may remove all the triangles on the same vertex set as the removed triangle. This fact in combination with Lemma 2.5 implies strong polynomial-time computation for a minimal FES $\mathcal {F}$ in $\mathcal {H}_{G}$ whose weighted cardinality $|\mathcal {F}|_{w}$ satisfies the following corollary.

Corollary 3.5

Given any linear triangle hypergraph $\mathcal {H}=(\mathcal {V},\mathcal {E})$ and any $\mathbf {w}\in \mathbb {Z}_{>0}^{\mathcal {V}}$, if $\mathcal {H}$ consists of p components, then a FES $\mathcal {F}$ of$\mathcal {H}$ with$|\mathcal {F}|_{w}\leq 2|\mathcal {E}|_{w}-|\mathcal {V}|_{w}+p$ can be found in $O(|\mathcal {E}|^{2})$ time.

3.2 Graphs with large weighted triangle packing numbers

We investigate (weighted) Tuza’s conjecture for graphs with large weighted packing numbers, which are firstly compared with the weighted number of triangles, and then with the weighted number of edges.

3.2.1 Comparing with the weighted number of triangles

Theorem 3.6

Let G be a simple graph and $\mathbf {w}\in \mathbb {Z}_{>0}^{E(G)}$. If real number c ∈ (0,1]satisfies $\nu _{t}(G,\mathbf {w})/|{\mathscr {T}}_{G}|_{w}\ge c$, then a triangle cover of (G, w) with weight at most $\frac {3c + 1}{3c}\nu _{t}(G,\mathbf {w})$ can be found in $O(|{\mathscr {T}}_{G}|^{3})$time. Consequently, $\tau _{t}(G,\mathbf {w})/\nu _{t}(G,\mathbf {w})\le \frac {3c + 1}{3c}$.

Proof

We consider the triangle hypergraph $\mathcal {H}_{G}=(E,{\mathscr {T}}_{G})$ of G, which is 3-uniform and linear. By Theorem 3.4, we can find in $O(|{\mathscr {T}}_{G}|^{3})$ time a FVS $\mathcal {S}$ of $\mathcal {H}_{G}$ with $|\mathcal {S}|_{w}\le |{\mathscr {T}}_{G}|_{w}/3$. Since $\nu (\mathcal {H}_{G},\mathbf {w})= \nu _{t}(G,\mathbf {w})\ge c|{\mathscr {T}}_{G}|_{w}$, it follows that $|\mathcal {S}|_{w}\le \nu (\mathcal {H}_{G},\mathbf {w})/(3c)$. As $\mathcal {H}_{G}\setminus \mathcal {S}$ is acyclic, Theorem 2.6 enables us to find in $O(|{\mathscr {T}}_{G}|^{2}\log ^{2}|{\mathscr {T}}_{G}|)$ time a minimum weighed transversal $\mathcal {R}$ of $\mathcal {H}_{G}\setminus \mathcal {S}$ such that $|\mathcal {R}|_{w}=\tau (\mathcal {H}_{G}\setminus \mathcal {S},\mathbf {w}|_{E-\mathcal {S}})=\nu (\mathcal {H}_{G}\setminus \mathcal {S},\mathbf {w}|_{E-\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 weight

$$|\mathcal{S}\cup\mathcal{R}|_{w} \leq \frac{\nu(\mathcal{H}_{G},\mathbf{w})}{3c}+\nu(\mathcal{H}_{G}\setminus\mathcal{S},\mathbf{w}|_{E-\mathcal{S}}) \leq\frac{3c + 1}{3c}\nu(\mathcal{H}_{G},\mathbf{w})=\frac{3c + 1}{3c}\nu_{t}(G,\mathbf{w}),$$

which proves the theorem. □

The special case of c = 1/3 in the above theorem gives the following result providing a new sufficient condition for the weighted version of Tuza’s conjecture.

Corollary 3.7

If simple graph G and edge weight $\mathbf {w}\in \mathbb {Z}_{+}^{E(G)}$ satisfythe inequality $\nu _{t}(G,\mathbf {w})/|{\mathscr {T}}_{G}|_{w}\ge 1/3$, then τ _t (G, w)/ν _t (G, w) ≤ 2.

The unweighted case

In the special case of unit weight, the condition $\nu _{t}(G)\ge |{\mathscr {T}}_{G}|/3$ in Corollary 3.7 applies, in some sense, only to the class of large scale sparse simple graphs (which, e.g., does not include complete graphs on four or more vertices). The mapping from the real number c in the condition $\nu _{t}(G)\ge c|{\mathscr {T}}_{G}|$ to the coefficient $\frac {3c + 1}{3c}$ in the conclusion $\tau _{t}(G)\le \frac {3c + 1}{3c}\nu _{t}(G)$ of Theorem 3.6 shows the trade-off between conditions and conclusions. As in Corollary 3.7, $c = \frac {1}{3}$ maps to $\frac {3c + 1}{3c} = 2$ hitting the boundary of Tuza’s conjecture. It remains to study graphs G with $\nu _{t}(G)/|{\mathscr {T}}_{G}|<\frac {1}{3}$. The next theorem (Theorem 3.8) tells us that actually 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 𝜖 can be any arbitrarily small positive number. So, in some sense, to solve Tuza’s conjecture as well as its weighted generalization, 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 $\frac {3c + 1}{3c} = \frac 73 = 2.333{\ldots }$, which is much better than the best known general bound 2.87 due to Haxell [3]. Only when $c \leq \frac 16$ does $\frac {3c + 1}{3c}$ state a trivial bound equal to or greater than 3.

Theorem 3.8

If there exists some real δ > 0such that Conjecture 1.1 holds for every simple graph (resp. multigraph) G with$\nu _{t}(G)/|{\mathscr {T}}_{G}|\ge 1/4-\delta$, then Conjecture 1.1 holds for every simple graph (resp. multigraph).

Proof

If $\delta \geq \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 − δ = i/j for some $i,j\in \mathbb {Z}_{>0}$. Therefore i/j < 1/4 gives 4i + 1 ≤ j, i.e., 4 + 1/i ≤ j/i. It remains to prove that for any graph G with $\nu _{t}(G)<(i/j)|{\mathscr {T}}_{G}|$ there holds τ _t (G) ≤ 2ν _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₄. Clearly, $|{\mathscr {T}}_{G^{\prime }}|=|{\mathscr {T}}_{G}|+k|{\mathscr {T}}_{K_{4}}|=|{\mathscr {T}}_{G}|+ 4k$, τ _t (G^′) = τ _t (G) + k ⋅ τ _t (K₄) = τ _t (G) + 2k and ν _t (G^′) = ν _t (G) + k ⋅ ν _t (K₄) = ν _t (G) + k. It follows that

$$\begin{array}{@{}rcl@{}} (i/j)|{\mathscr{T}}_{G^{\prime}}|&=&(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)\text{{{\textit{k}}}})\\ &\le& \nu_{t}(G)+k\\ &=& \nu_{t}(G^{\prime}) \end{array} $$

where the inequality is guaranteed by 4 + 1/i ≤ j/i. So $\nu _{t}(G^{\prime })\ge (1/4-\delta )|{\mathscr {T}}_{G^{\prime }}|$ together with the hypothesis of the theorem implies τ _t (G^′) ≤ 2ν _t (G^′), i.e., τ _t (G) + 2k ≤ 2(ν _t (G) + k), giving τ _t (G) ≤ 2ν _t (G) as desired. □

In the proof of the above theorem, the properties of K₄ that $\nu _{t}(K_{4})/|{\mathscr {T}}_{K_{4}}|= 1/4$ and τ _t (K₄)/ν _t (K₄) = 2 plays an important role. It helps to reduce the general (weighted) Tuza’s conjecture to the special case where $\nu _{t}(G)\ge (1/4-\delta )|{\mathscr {T}}_{G}|$. We emphasize that the statement for multigraphs in Theorem 3.8 amounts to an equivalent result for Conjecture 1.2, because Conjecture 1.1 true for multigraphs is equivalent to Conjecture 1.2 true for weighted simple graphs.

More efficient computation for unweighted simple graphs

Given a graph G and an edge subset F ⊆ E(G), we use G[F] to denote the subgraph G induced by F. We call Gtriangle-divisible if E(G) admits a nontrivial partition (E₁, E₂) such that $({\mathscr {T}}_{G[E_{1}]},{\mathscr {T}}_{G[E_{2}]})$ is a nontrivial partition of ${\mathscr {T}}_{G}$, and call Gtriangle-indivisible, otherwise. For example, in Fig. 7, the left graph is triangle-indivisible, but the right graph is not (where partitioning edges into thick ones and bold ones shows its triangle divisibility). The following are straightforward observations.

Fig. 7

Examples for triangle (in)divisibility

Observation 3.9

• (i) An irreducible nonempty graph G = (V, E) is triangle-indivisible if and only if its associated triangle hypergraph $\mathcal {H}_{G}=(E,{\mathscr {T}}_{G})$ is connected.

• (ii) Conjecture 1.1 is true if the conjectured inequality holds for every triangle-indivisible simple graph.

For simple graphs G, with the help of Algorithm 2 we can improve the $O(|{\mathscr {T}}_{G}|^{3})$ time complexity stated in Theorem 3.6.

Corollary 3.10

Let G = (V, E) be a simple triangle-indivisible graph, if $\nu _{t}(G)/ |{\mathscr {T}}_{G}|\geq 1/3$, then a triangle cover of G with cardinality at most2ν _t (G) can be found in $O(|E|(|{\mathscr {T}}_{G}|+|E|\log |E|)\log |E|)$ time.

Proof

We consider the triangle hypergraph $\mathcal {H}_{G}=(E,{\mathscr {T}}_{G})$ of G, which is 3-uniform and linear. Note from Observation 3.9(i) that $\mathcal {H}_{G}=(E,{\mathscr {T}}_{G})$ is connected. Thus by Corollary 2.11, we obtain in $O(|E|(|{\mathscr {T}}_{G}|+|E|\log |E|)\log |E|)$ time a triangle cover of G with cardinality at most $\frac {2|{\mathscr {T}}_{G}|+ 1}{3}\le 2\nu _{t}(G)+\frac {1}{3}$. □

3.2.2 Comparing with the weighted number of edges

The sufficient condition that compares the weighted triangle packing number with the weights of edges is based on the fact that every edge-weighted simple graph (G, w) has a bipartite subgraph whose edges have a total weight at least |E(G)| _w /2, and such a bipartite subgraph can be found in strongly polynomial time. Since this subgraph does not contain any triangle, we deduce that τ _t (G, w) ≤|E| _w /2, which implies the following result.

Corollary 3.11

Let G = (V, E) be a graph with edge weight $\mathbf {w}\in \mathbb {Z}_{>0}^{E}$. If ν _t (G, w)/|E| _w ≥ cfor some c > 0, then τ _t (G, w)/ν _t (G, w) ≤ 1/(2c) . In particular, if ν _t (G, w)/|E| _w ≥ 1/4, then τ _t (G, w)/ν _t (G, w) ≤ 2.

Thus if ν _t (G, w)/|E| _w ≥ c for some c > 0, then a triangle cover of G with weight at most ν _t (G, w)/(2c) can be found in strongly polynomial time. When restricted to unweighted simple graphs, complementary to Corollary 3.7 whose condition mainly takes care of sparse graphs, the second statement of Corollary 3.11 applies to many dense graphs, including all complete graphs of order at least 3 other than K₅ (see Theorem 2 in [14]).

Similarly to Corollary 3.7 and Theorem 3.8, by which our future investigation space on (weighted) Tuza’s conjecture shrinks to interval $(\frac {1}{4}-\epsilon ,\frac {1}{3})$ w.r.t. $\nu _{t}(G,\mathbf {w})/|{\mathscr {T}}_{G}|_{w}$, Corollary 3.11 and the following Theorem 3.12 narrow the interval w.r.t. ν _t (G, w)/|E| _w to $(\frac 15-\epsilon ,\frac {1}{4})$. Moreover, when taking $c = \frac 15$ in Corollary 3.11. we obtain $\frac {1}{2c} = 2.5$, still better than Haxell’s general bound 2.87 for unweighted simple graphs [3].

Theorem 3.12

If there exists some real δ > 0such that Conjecture 1.1 holds for every simple graph (resp. multigraph) G withν _t (G)/|E(G)|≥ 1/5 − δ, then Conjecture 1.1 holds for every simple graph (resp. multigraph).

Proof

We use a similar trick to that in proving Theorem 3.8; 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 − δ = i/j for some $i,j\in \mathbb {Z}_{>0}$. Therefore i/j < 1/5 and the integrality of i, j imply 5 + 1/i ≤ j/i. To prove Tuza’s conjecture for each graph G with ν _t (G) < (i/j)|E|, we write $k=i|E|-j\cdot \nu _{t}(G)\in \mathbb {Z}_{>0}$. Let G^′ = (V^′, E^′) be the disjoint union of G and k copies of K₅’s. Then |E^′| = |E| + 10k, τ _t (G^′) = τ _t (G) + k ⋅ τ _t (K₅) = τ _t (G) + 4k, ν _t (G^′) = ν _t (G) + k ⋅ ν _t (K₅) = ν _t (G) + 2k, and

$$(i/j)|E^{\prime}|\!=(i/j)(|E|+ 10k) \!=(i/j)(j\cdot\nu_{t}(G)/i+(10 + 1/i)k)\le \nu_{t}(G)+ 2k= \nu_{t}(G^{\prime})$$

where the inequality is guaranteed by 10 + 1/i ≤ 2j/i. So ν _t (G^′) ≥ (1/5 − δ)|E^′| together with the hypothesis the theorem implies τ _t (G^′) ≤ 2ν _t (G^′), i.e., τ _t (G) + 4k ≤ 2(ν _t (G) + 2k), giving τ _t (G) ≤ 2ν _t (G) as desired. □

Erdős-Rényi graphs with high densities

As an application of Corollary 3.11 we investigate Tuza’s conjecture on random graphs. Let n be a positive integer and let p ∈ [0,1]. The Erdős-Rényi random graph model [15] is a probability space over the set $\mathcal {G}(n,p)$ of simple graphs G = (V, E) on the vertex set V = {1,…,n}, where an edge between vertices i and j is included in E with probability p independently from every other possible edge, i.e.,

$$\textbf{Pr}[ij\in E]=p\text{ for each pair of distinct\ } i,j\in V.$$

The $\mathcal {G}(n,p)$ model is often used in the probabilistic method for tackling problems in various areas such as graph theory and combinatorial optimization.

The following result on the triangle packing numbers of complete graphs [16] is useful in deriving a good estimation for the triangle packing numbers of graphs in $\mathcal {G}(n,p)$.

Theorem 3.13 (16)

ν _t (K _n ) = |E(K _n )|/3if and only if n ≡ 1,3 (mod 6) .

Theorem 3.14

Suppose that $p> \sqrt {3}/2$ and$G=(V,E)\in \mathcal {G}(n,p)$. Then Pr[ν _t (G) ≥|E|/4] = 1 − o(1) and Pr(τ _t (G) ≤ 2ν _t (G)) = 1 − o(1) .

Proof

Let K _n denote the complete graph on V. For each edge e ∈ K _n , let X _e be the indicator variable satisfying: X _e = 1 if e ∈ E and X _e = 0 otherwise. Thus E[X _e ] = p, $X={\sum }_{e\in K_{n}}X_{e}=|E|$, E[X] = n(n − 1) p/2. Since X _e , e ∈ K _n , are independent 0-1 variables, by Chernoff Bounds [15], for each 𝜖 ∈ (0,1], Pr[X > (1 + 𝜖)E[X]] ≤ exp(−𝜖²E[X]/3) = exp(−𝜖²n(n − 1) p/6) = o(1). So

$$\textbf{Pr}[X\leq (1+\epsilon)\textbf{E}[X]]= \textbf{Pr}(X\leq (1+\epsilon)n(n-1)p/2) = 1-o(1).$$

On the other hand, by Theorem 3.13, we can make K _n have an edge-disjoint triangle decomposition by deleting at most three vertices, which implies that ν _t (K _n ) is lower bounded by k = ⌈(n − 3)(n − 4)/6⌉. Thus we can take k edge-disjoint triangles T₁,…,T _k from K _n . For each i ∈ [k], let Y _i be the indicator variable satisfying: Y _i = 1 if T _i ⊆ G and Y _i = 0 otherwise. Note that E[Y _i ] = p³ for each i ∈ [k], $\nu _{t}(G)\geq Y = {\sum }_{i = 1}^{k}Y_{i}$ and E[Y ] = kp³. Because T₁,…,T _k are edge-disjoint, Y₁,…,Y _k are independent 0-1 variables. By Chernof f Bounds, for each 𝜖 ∈ (0,1), Pr[Y < (1 − 𝜖)E[Y ]] ≤ exp(−𝜖²E[Y ]/2) ≤ exp(−𝜖²(n − 3)(n − 4) p³/12) = o(1).Thus

$$\textbf{Pr}[\nu_{t}(G)\geq (1-\epsilon)(n-3)(n-4)p^{3}/6]\ge\textbf{Pr}[\nu_{t}(G)\geq (1-\epsilon)kp^{3}]\ge\textbf{Pr}[Y\geq (1-\epsilon)\textbf{E}[Y]]= 1-o(1). $$

Recall that $p> \sqrt {3}/2$. We can take 𝜖 ∈ (0,1) such that $\lim _{n\rightarrow \infty }\frac {(1-\epsilon )(n-3)(n-4)p^{3}/6}{(1+\epsilon )n(n-1)p/8}= \frac {4p^{2}(1-\epsilon )}{3(1+\epsilon )}> 1$. So for sufficient large n, we have (1 − 𝜖)(n − 3)(n − 4) p³/6 > (1 + 𝜖) n(n − 1) p/8. Since we have ν _t (G) ≥ (1 − 𝜖)(n − 3)(n − 4) p³/6 with probability 1 − o(1) and have |E| = X ≤ (1 + 𝜖) n(n − 1) p/2 with probability 1 − o(1), we obtain ν _t (G) ≥|E|/4 with probability 1 − o(1). It follows from Corollary 3.11 that Pr(τ _t (G) ≤ 2ν _t (G)) = 1 − o(1). □

3.3 Graphs with large weighted numbers of edges

Each graph has a unique maximum irreducible subgraph. Tuza’s conjecture, as well as its weighted generalization, is valid for a graph if and only if the conjecture is valid for its maximum irreducible subgraph. In this section, we study sufficient conditions for (weighted) Tuza’s conjecture on irreducible graphs that bound the (weighted) number of edges below in terms of the (weighted) number of triangles.

Theorem 3.15

Let G be an irreducible simple graph and$\mathbf {w}\in \mathbb {Z}_{>0}^{E(G)}$. If $|E|_{w}/|{\mathscr {T}}_{G}|_{w}\ge 2$, then a triangle cover of (G, w) with weight at most 2ν _t (G, w) can be found in $O(|{\mathscr {T}}_{G}|^{2}\log ^{2}|{\mathscr {T}}_{G}|)$ time. Consequently, implies τ _t (G, w)/ν _t (G, w) ≤ 2.

Proof

Recall that the irreducibility of G implies $|E|\le 3|{\mathscr {T}}_{G}|$. Suppose that the linear 3-uniform hypergraph $\mathcal {H}_{G}=(E,{\mathscr {T}}_{G})$ associated to G has exactly p components. By Corollary 3.5, we can find in $O(|{\mathscr {T}}_{G}|^{2})$ time a minimal FES $\mathcal {F}$ of $\mathcal {H}_{G}$ such that $|\mathcal {F}|_{w}\leq 2|{\mathscr {T}}_{G}|_{w}-|E|_{w}+p\le p$. Since G is irreducible, we see that $\mathcal {H}_{G}$ has no isolated vertices, i.e., every component of $\mathcal {H}_{G}$ has at least one edge. Thus $\nu (\mathcal {H}_{G},\mathbf {w})\geq p\geq |\mathcal {F}|_{w}$. For the acyclic hypergraph $\mathcal {H}_{G}\setminus \mathcal {F}$, by Theorem 2.6 we may find in $O(|{\mathscr {T}}_{G}|^{2}\log ^{2}|{\mathscr {T}}_{G}|)$ time a minimum weighted transversal $\mathcal {R}$ of $\mathcal {H}_{G}\setminus \mathcal {F}$ such that

$$|\mathcal{R}|_{w}=\tau(\mathcal{H}_{G}\setminus\mathcal{F},\mathbf{w})=\nu(\mathcal{H}_{G}\setminus\mathcal{F},\mathbf{w}).$$

Observe that $\mathcal {R}\subseteq E$ and $\mathcal {F}\subseteq {\mathscr {T}}_{G}$. For each $F\in \mathcal {F}$, take e _F ∈ E with e _F ∈ 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 weight $|\mathcal {R}\cup \mathcal {S}|_{w}\leq \nu (\mathcal {H}_{G}\setminus \mathcal {F},\mathbf {w})+ |\mathcal {F}|_{w} \leq 2\nu (\mathcal {H}_{G},\mathbf {w})= 2\nu _{t}(G,\mathbf {w})$, establishing the theorem. □

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

Along the same line as in the preceeding subsection, regarding weighted Tuza’s conjecture on graph G, Theorem 3.15 and the following Theorem 3.16 jointly narrow the interval w.r.t. $|E(G)|_{w}/|{\mathscr {T}}_{G}|_{w}$ to (1.5 − 𝜖,2) for future study.

Theorem 3.16

If there exists some real δ > 0 such that Conjecture 1.1 holds for every irreducible simple graph (resp. multigraph) G = (V, E) with $|E|/|{\mathscr {T}}_{G}|\ge 3/2-\delta$, then Conjecture 1.1 holds for every irreducible simple graph (resp. multigraph), and therefore holds for every simple graph (resp. multigraph).

Proof

Again we apply the trick of adding copies of K₄. We may assume $\delta \in (0,3/2)\cap \mathbb {Q}$ and 3/2 − δ = i/j for some $i,j\in \mathbb {Z}_{>0}$. Therefore 2i + 1 ≤ 3j, implying (i/j)(4 + 1/i) ≤ 6.

For any irreducible graph G with $|E|<(i/j)|{\mathscr {T}}_{G}|$, we write $k=i|{\mathscr {T}}_{G}|-j|E|\in \mathbb {Z}_{>0}$. Let G^′ be the disjoint union of G and k copies of K₄. Then G^′ is irreducible, and

$$(i/j)|{\mathscr{T}}_{G^{\prime}}|=(i/j)(|{\mathscr{T}}_{G}|+ 4k)=(i/j)(j|E|/i+(4 + 1/i)k)\le |E|+ 6k= |E^{\prime}|.$$

It follows from the hypothesis of the theorem that τ _t (G^′) ≤ 2ν _t (G^′), i.e., τ _t (G) + 2k ≤ 2(ν _t (G) + k), giving τ _t (G) ≤ 2ν _t (G) as desired. □

4 Conclusion

Using tools from hypergraphs, we design strongly polynomial-time algorithms for finding small (weighted) triangle covers in graphs, which particularly imply several sufficient conditions for Tuza’s conjecture (Conjecture 1.1) and its weighted version (Conjecture 1.2).

Triangle packing and covering

In this paper, we have established new sufficient conditions $\nu _{t}(G,\mathbf {w})/|{\mathscr {T}}_{G}|_{w}\ge 1/3$ and $|E|_{w}/|{\mathscr {T}}_{G}|_{w}\ge 2$ for weighted Tuza’s conjecture on packing and covering triangles in graphs G. We prove the sufficiency by designing polynomial-time combinatorial algorithms for finding a triangle cover of G whose weight (i.e., weighted cardinality) is upper bounded by 2ν _t (G, w). 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 2.1 and 3.15), which guarantees that the remaining graph has equal weighted triangle covering number and weighted triangle packing number, and a minimum weighted triangle cover of the remaining graph is computable in strongly polynomial time (see Theorem 2.6). It is well known that the acyclic condition in Theorem 2.6 could be weakened to odd-cycle-freeness [11]. So the lower bound 1/3 and 2 in the sufficient conditions could be (significantly) improved if we can remove edges of a (much) less total weight from G such that the triangle hypergraph of the remaining graph is odd-cycle free.

In view of Theorems 3.8, 3.12, and 3.16, the study on the graphs (G, w) satisfying $\nu _{t}(G,\mathbf {w}) / |{\mathscr {T}}_{G}|_{w}\ge 1/4$ or ν _t (G, w)/|E| _w ≥ 1/5 or $|E|_{w}/|{\mathscr {T}}_{G}|_{w}\ge 3/2$ might suggest more insight and foresight for resolving (weighted) Tuza’s conjecture. These graphs are critical in the sense that they are standing on the border of the resolution.

Regarding Theorem 3.6, Corollary 3.11, and Theorem 3.15, Gregory J. Puleo made a nice observation that $\nu _{t}(G)/ |{\mathscr {T}}_{G}|\leq 1/3$, ν _t (G)/|E|≤ 1/4, and $|E|/|{\mathscr {T}}_{G}|\leq 2$ hold for every irreducible extremal graph G = (V, E) – simple graphs satisfying Tuza’s conjecture with tight ratio τ _t (G)/ν _t (G) = 2. So studying extremal graphs might lead to interesting results.

Another intermediate step toward resolving Tuza’s conjecture is investigating its validity for the classical Erdős-Rényi random graph model $\mathcal {G}(n,p)$. In this paper, we have shown that Tuza’s conjecture holds with high probability for graphs in $\mathcal {G}(n,p)$ when $p> \sqrt {3}/2$. It would be nice to prove the same result for $p\in (0,\sqrt 3/2]$.

The generalization to linear 3-uniform hypergraphs

Our work has shown very close relations between triangle packing and covering in graphs and edge (resp. cycle) packing and covering in linear 3-uniform hypergraphs. The theoretical and algorithmic results on linear 3-uniform hypergraphs (Corollary 2.3 and Lemma 2.5) are crucial for us to establish sufficient conditions for Tuza’s conjecture, and to find in polynomial time a “small” triangle cover under the conditions (see Corollary 3.7 and Theorem 3.15). Recall that, for any simple graph G, its triangle hypergraph $\mathcal {H}_{G}$ is linear 3-uniform, and Tuza’s conjecture is equivalent to $\tau (\mathcal {H}_{G})\leq 2\nu (\mathcal {H}_{G})$. As a natural generalization, one may ask: Does $\tau (\mathcal {H})\leq 2\nu (\mathcal {H})$ hold for all linear 3-uniform hypergraphs $\mathcal {H}$? The answer is negative – as Zbigniew Lonc noticed, the hypergraph of Fano plane is a linear 3-uninform hypergraph with transversal number 3 and matching number 1.

Last but not the least, the arguments in this paper have actually proved the following stronger result on 3-uniform hypergraphs.

Theorem 4.1

Let $\mathcal {H}=(\mathcal {V},\mathcal {E})$ be a linear 3-uniform hypergraph without isolated vertices, and $\mathbf {w}\in \mathbb {Z}_{>0}^{\mathcal {V}}$ . Then a transversal of $\mathcal {H}$ with weight at most $2\nu (\mathcal {H},\mathbf {w})$ can be found in strongly polynomial time, which implies $\tau (\mathcal {H},\mathbf {w})\le 2\nu (\mathcal {H},\mathbf {w})$ , if one of the following conditions is satisfied:

• (i) $\nu (\mathcal {H},\mathbf {w})/|\mathcal {E}|_{w}\ge 1/3$ ,

• (ii) $|\mathcal {V}|_{w}/|\mathcal {E}|_{w}\ge 2$ .

Comparing the above result on linear 3-uniform hypergraphs $\mathcal {H}$ with its counterpart on simple graphs presented in Theorem 1.4, one might notice that the condition on the lower bound of $\nu (\mathcal {H},\mathbf {w})/|\mathcal {V}|_{w}$ is missing. This reason is that we do not have a nontrivial constant upper bound on $\tau (\mathcal {H},\mathbf {w})/|\mathcal {V}|_{w}$. Again, Theorem 4.1 implies the same result for unit-weighted 3-uniform hypergraphs $\mathcal {H}$ which may not be linear.