Covering Triangles in Edge-Weighted Graphs

Let G = (V, E) be a simple graph and (Formula presented.) 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 (Formula presented.). 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 (Formula presented.) consisting of edge sets of triangles in G. Let (Formula presented.) and (Formula presented.) 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) (Formula presented.), (ii) (Formula presented.), (iii) (Formula presented.).