On approximate graph colouring and max-k-cut algorithms based on the θ-function

The problem of colouring a k-colourable graph is well-known to be NP-complete, for k ≥ 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 s...

Full description

Saved in:
Bibliographic Details
Main Authors: Klerk, Etienne de., Pasechnik, Dmitrii V., Warners, J. P.
Other Authors: School of Physical and Mathematical Sciences
Format: Article
Language:English
Published: 2013
Subjects:
Online Access:https://hdl.handle.net/10356/95230
http://hdl.handle.net/10220/9275
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
id sg-ntu-dr.10356-95230
record_format dspace
spelling sg-ntu-dr.10356-952302023-02-28T19:28:24Z On approximate graph colouring and max-k-cut algorithms based on the θ-function Klerk, Etienne de. Pasechnik, Dmitrii V. Warners, J. P. School of Physical and Mathematical Sciences DRNTU::Science::Mathematics The problem of colouring a k-colourable graph is well-known to be NP-complete, for k ≥ 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 Lovász θ-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 θ-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 Lovász θ-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 ≫ 0. Accepted version 2013-02-27T04:05:24Z 2019-12-06T19:10:51Z 2013-02-27T04:05:24Z 2019-12-06T19:10:51Z 2004 2004 Journal Article Klerk, E. d., Pasechnik, D. V., & Warners, J. P. (2004). On Approximate Graph Colouring and MAX-k-CUT Algorithms Based on the θ-Function. Journal of Combinatorial Optimization, 8(3), 267-294. 1382-6905 https://hdl.handle.net/10356/95230 http://hdl.handle.net/10220/9275 10.1023/B:JOCO.0000038911.67280.3f en Journal of combinatorial optimization © 2004 Kluwer Academic Publishers. This is the author created version of a work that has been peer reviewed and accepted for publication by Journal of Combinatorial Optimization, Kluwer Academic Publishers. It incorporates referee’s comments but changes resulting from the publishing process, such as copyediting, structural formatting, may not be reflected in this document. The published version is available at: DOI[http://dx.doi.org/10.1023/B:JOCO.0000038911.67280.3f] . application/pdf
institution Nanyang Technological University
building NTU Library
continent Asia
country Singapore
Singapore
content_provider NTU Library
collection DR-NTU
language English
topic DRNTU::Science::Mathematics
spellingShingle DRNTU::Science::Mathematics
Klerk, Etienne de.
Pasechnik, Dmitrii V.
Warners, J. P.
On approximate graph colouring and max-k-cut algorithms based on the θ-function
description The problem of colouring a k-colourable graph is well-known to be NP-complete, for k ≥ 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 Lovász θ-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 θ-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 Lovász θ-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 ≫ 0.
author2 School of Physical and Mathematical Sciences
author_facet School of Physical and Mathematical Sciences
Klerk, Etienne de.
Pasechnik, Dmitrii V.
Warners, J. P.
format Article
author Klerk, Etienne de.
Pasechnik, Dmitrii V.
Warners, J. P.
author_sort Klerk, Etienne de.
title On approximate graph colouring and max-k-cut algorithms based on the θ-function
title_short On approximate graph colouring and max-k-cut algorithms based on the θ-function
title_full On approximate graph colouring and max-k-cut algorithms based on the θ-function
title_fullStr On approximate graph colouring and max-k-cut algorithms based on the θ-function
title_full_unstemmed On approximate graph colouring and max-k-cut algorithms based on the θ-function
title_sort on approximate graph colouring and max-k-cut algorithms based on the θ-function
publishDate 2013
url https://hdl.handle.net/10356/95230
http://hdl.handle.net/10220/9275
_version_ 1759856292100308992