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 alphapartially kcolorable, if there exists a subset S subset V of cardinality S >= alpha V such that the graph induced on S is kcolorable. Partial kcolorability is a more robust structural property of a graph than kcolorability. For graphs that arise in practice, partial kcolorability might be a better notion to use than kcolorability, 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 3colorable 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 semirandom families of instances of partially 3colorable graphs and partially 2colorable graphs, and give stronger bicriteria 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:128:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771252},
ISSN = {18688969},
year = {2019},
volume = {145},
editor = {Dimitris Achlioptas and L{\'a}szl{\'o} A. V{\'e}gh},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11243},
URN = {urn:nbn:de:0030drops112438},
doi = {10.4230/LIPIcs.APPROXRANDOM.2019.28},
annote = {Keywords: Approximation Algorithms, Vertex Coloring, Semirandom Models}
}
17.09.2019
Keywords: 

Approximation Algorithms, Vertex Coloring, Semirandom Models 
Seminar: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)

Issue date: 

2019 
Date of publication: 

17.09.2019 