Back to Search Start Over

Covering Triangles in Edge-Weighted Graphs.

Authors :
Chen, Xujin
Diao, Zhuo
Hu, Xiaodong
Tang, Zhongzheng
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]

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