Approximating the maximum 3-edge-colorable subgraph problem
Approximating the maximum 3-edge-colorable subgraph problem
复制标题
近似最大 3 边可着色子图问题
DOI：
10.1016/j.disc.2008.11.017
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Romeo Rizzi
中科院分区：
文献类型：
--
作者：
Romeo Rizzi
我们给出了如下结构性结果：每个最大度为3的无三角形图G有3个匹配，它们至少覆盖了（1−23γo（G））条边，其中γo（G）表示G的奇围长.特别地，每个最大度为3的无三角形图G都有3个匹配，这些匹配至少覆盖它的13/15条边。Petersen图，我们可以对它的15条边中的最多13条边进行3边着色，表明这是紧的。我们也可以通过3个匹配覆盖任何最大度为3的简单图的至少6/7的边;这也是一个紧界。对于一个固定的参数k≥1，最大k边可着色子图问题要求对输入的简单图的大部分边进行k边着色。已知对于所有k≥2，该问题是APX困难的。然而，随着k趋于无穷大，近似比趋于1的近似算法也是已知的。目前，对于k=2和k=3的情况，最好的已知性能比分别为5/6和4/5。由于我们的结构结果的证明是算法性的，因此我们获得了k=3情况下的改进近似算法，实现了6/7的近似比。更好的界限，并允许平行的边缘，获得更高的奇数围长的图（例如， 当输入多重图被限制为无三角形时，边界为13/15，当C5也被禁止时，边界为19/21）。
We offer the following structural result: every triangle-free graph G of maximum degree 3 has 3 matchings which collectively cover at least (1−23γo(G)) of its edges, where γo(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 APX-hard for all k≥2. However, approximation algorithms with approximation ratios tending to 1 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 C5’s are also banned).