We offer the following structural result: every triangle-free graph G of maximum degree 3 has 3 matchings which collectively cover at least (1 - 2/3 gamma(0)(G)) of its edges, where gamma(0)(G) denotes the odd girth of G. In particular, every triangle-free graph G of maximum degree 3 has 3 matchings which cover at least 13/15 of its edges. The Petersen graph, where we can 3-edge-color at most 13 of its 15 edges, shows this to be tight. We can also cover at least 6/7 of the edges of any simple graph of maximum degree 3 by means of 3 matchings; again a tight bound. For a fixed value of a parameter k >= 1, the Maximum k-Edge-Colorable Subgraph Problem asks to k-edge-color the most of the edges of a simple graph received in input. The problem is known to be ARX-hard for all k >= 2. However, approximation algorithms with approximation ratios tending to I as k goes to infinity are also known. At present, the best known performance ratios for the cases k = 2 and k = 3 were 5/6 and 4/5, respectively. Since the proofs of our structural result are algorithmic, we obtain an improved approximation algorithm for the case k = 3, achieving approximation ratio of 6/7. Better bounds, and allowing also for parallel edges, are obtained for graphs of higher odd girth (e.g., a bound of 13/15 when the input multigraph is restricted to be triangle-free, and of 19/21 when C(5)'s are also banned).
Approximating the maximum 3-edge-colorable subgraph problem.
RIZZI, ROMEO
2009-01-01
Abstract
We offer the following structural result: every triangle-free graph G of maximum degree 3 has 3 matchings which collectively cover at least (1 - 2/3 gamma(0)(G)) of its edges, where gamma(0)(G) denotes the odd girth of G. In particular, every triangle-free graph G of maximum degree 3 has 3 matchings which cover at least 13/15 of its edges. The Petersen graph, where we can 3-edge-color at most 13 of its 15 edges, shows this to be tight. We can also cover at least 6/7 of the edges of any simple graph of maximum degree 3 by means of 3 matchings; again a tight bound. For a fixed value of a parameter k >= 1, the Maximum k-Edge-Colorable Subgraph Problem asks to k-edge-color the most of the edges of a simple graph received in input. The problem is known to be ARX-hard for all k >= 2. However, approximation algorithms with approximation ratios tending to I as k goes to infinity are also known. At present, the best known performance ratios for the cases k = 2 and k = 3 were 5/6 and 4/5, respectively. Since the proofs of our structural result are algorithmic, we obtain an improved approximation algorithm for the case k = 3, achieving approximation ratio of 6/7. Better bounds, and allowing also for parallel edges, are obtained for graphs of higher odd girth (e.g., a bound of 13/15 when the input multigraph is restricted to be triangle-free, and of 19/21 when C(5)'s are also banned).
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
