Back to Search
Start Over
Covering Triangles in Edge-Weighted Graphs.
- Source :
-
Theory of Computing Systems . Aug2018, Vol. 62 Issue 6, p1525-1552. 28p. - Publication Year :
- 2018
-
Abstract
- Let G = (V, E) be a simple graph and w∈ℤ>0E<inline-graphic></inline-graphic> 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 w∈ℤ>0E<inline-graphic></inline-graphic>. 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 TG<inline-graphic></inline-graphic> consisting of edge sets of triangles in G. Let |E|w=∑e∈Ew(e)<inline-graphic></inline-graphic> and |TG|w=∑{e,f,g}∈TGw(e)w(f)w(g)<inline-graphic></inline-graphic> 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) νt(G,w)/|TG|w≥13<inline-graphic></inline-graphic>, (ii) νt(G,w)/|E|w≥14<inline-graphic></inline-graphic>, (iii) |E|w/|TG|w≥2<inline-graphic></inline-graphic>. [ABSTRACT FROM AUTHOR]
- Subjects :
- *GRAPH theory
*INTEGERS
*HYPERGRAPHS
*COMBINATORIAL group theory
*POLYNOMIALS
Subjects
Details
- Language :
- English
- ISSN :
- 14324350
- Volume :
- 62
- Issue :
- 6
- Database :
- Academic Search Index
- Journal :
- Theory of Computing Systems
- Publication Type :
- Academic Journal
- Accession number :
- 129928531
- Full Text :
- https://doi.org/10.1007/s00224-018-9860-7