License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.28
URN: urn:nbn:de:0030-drops-112438
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11243/
Go to the corresponding LIPIcs Volume Portal

Ghoshal, Suprovat ; Louis, Anand ; Raychaudhury, Rahul

Approximation Algorithms for Partially Colorable Graphs

pdf-format:
LIPIcs-APPROX-RANDOM-2019-28.pdf (0.6 MB)

Abstract

Graph coloring problems are a central topic of study in the theory of algorithms. We study the problem of partially coloring partially colorable graphs. For alpha <= 1 and k in Z^+, we say that a graph G=(V,E) is alpha-partially k-colorable, if there exists a subset S subset V of cardinality |S| >= alpha |V| such that the graph induced on S is k-colorable. Partial k-colorability is a more robust structural property of a graph than k-colorability. For graphs that arise in practice, partial k-colorability might be a better notion to use than k-colorability, since data arising in practice often contains various forms of noise.
We give a polynomial time algorithm that takes as input a (1 - epsilon)-partially 3-colorable graph G and a constant gamma in [epsilon, 1/10], and colors a (1 - epsilon/gamma) fraction of the vertices using O~(n^{0.25 + O(gamma^{1/2})}) colors. We also study natural semi-random families of instances of partially 3-colorable graphs and partially 2-colorable graphs, and give stronger bi-criteria approximation guarantees for these family of instances.

BibTeX - Entry

@InProceedings{ghoshal_et_al:LIPIcs:2019:11243,
  author =	{Suprovat Ghoshal and Anand Louis and Rahul Raychaudhury},
  title =	{{Approximation Algorithms for Partially Colorable Graphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{28:1--28:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Dimitris Achlioptas and L{\'a}szl{\'o} A. V{\'e}gh},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11243},
  URN =		{urn:nbn:de:0030-drops-112438},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.28},
  annote =	{Keywords: Approximation Algorithms, Vertex Coloring, Semi-random Models}
}

Keywords: Approximation Algorithms, Vertex Coloring, Semi-random Models
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Issue Date: 2019
Date of publication: 17.09.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI