On approximate graph colouring and MAX-k-CUT algorithms based on the υ-function
On approximate graph colouring and MAX-k-CUT algorithms based on the υ-function
复制标题
DOI：
10.1023/b:joco.0000038911.67280.3f
复制
发表时间：
2004-09-01
影响因子：
1
通讯作者：
Warners, JP
中科院分区：
文献类型：
--
作者：
De Klerk, E;Pasechnik, DV;Warners, JP
k-列图的着色问题是NP-完全的，其中k大于或等于3。近似k-着色的MAX-k-CUT方法是在多项式时间内将k种颜色分配给所有顶点，使得“缺陷边缘”（具有相同颜色的端点）的分数可证明是小的。Frieze和Jerrum（1997）使用与Lovasz θ函数相关的半定规划（SDP）松弛法获得了最著名的近似。在相关的工作中，Karger等人（1998）设计了近似算法，用于在多项式时间内用尽可能少的颜色对k-列图进行着色。他们还使用了SDP松弛相关的theta-function.In本文中，我们进一步探讨半定规划松弛图着色被视为一个可满足性问题，认为在德克勒克等人。（2000年）。我们首先证明了De Klerk et al.（2000）中提出的色数的近似是由Lovasz θ-函数从上到下有界的。De Klerk et al.（2000）中的半定规划松弛涉及近似空间的提升，这反过来又提出了一个可证明的好MAX-k-CUT算法。我们表明，我们的算法与Frieze和Jerrum的算法密切相关;因此，我们可以针对k的小固定值提高他们对MAX-k-CUT的近似保证。例如，如果k = 3，我们可以将它们的界限从0.832718提高到0.836008，对于k = 4，从0.850301提高到0.857487。我们还给出了Frieze-Jerrum舍入格式的一个新的渐近分析，当k远大于0时，它为Frieze和Jerrum（1997）以及Karger等人（1998）的主要结果提供了一个统一的证明。
The problem of colouring a k-colourable graph is well-known to be NP-complete, for k greater than or equal to 3. The MAX-k-CUT approach to approximate k-colouring is to assign k colours to all of the vertices in polynomial time such that the fraction of 'defect edges' ( with endpoints of the same colour) is provably small. The best known approximation was obtained by Frieze and Jerrum ( 1997), using a semidefinite programming ( SDP) relaxation which is related to the Lovasz theta-function. In a related work, Karger et al. ( 1998) devised approximation algorithms for colouring k-colourable graphs exactly in polynomial time with as few colours as possible. They also used an SDP relaxation related to the theta-function.In this paper we further explore semidefinite programming relaxations where graph colouring is viewed as a satisfiability problem, as considered in De Klerk et al. ( 2000). We first show that the approximation to the chromatic number suggested in De Klerk et al. ( 2000) is bounded from above by the Lovasz theta-function. The underlying semidefinite programming relaxation in De Klerk et al. ( 2000) involves a lifting of the approximation space, which in turn suggests a provably good MAX-k-CUT algorithm. We show that of our algorithm is closely related to that of Frieze and Jerrum; thus we can sharpen their approximation guarantees for MAX-k-CUT for small fixed values of k. For example, if k = 3 we can improve their bound from 0.832718 to 0.836008, and for k = 4 from 0.850301 to 0.857487. We also give a new asymptotic analysis of the Frieze-Jerrum rounding scheme, that provides a unifying proof of the main results of both Frieze and Jerrum ( 1997) and Karger et al. ( 1998) for k much greater than 0.