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/
Ghoshal, Suprovat ;
Louis, Anand ;
Raychaudhury, Rahul
Approximation Algorithms for Partially Colorable Graphs
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 |