Konrad, Christian ;
Zamaraev, Viktor
Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs
Abstract
We give deterministic distributed (1+epsilon)approximation algorithms for Minimum Vertex Coloring and Maximum Independent Set on chordal graphs in the LOCAL model. Our coloring algorithm runs in O( (1 / epsilon) log n) rounds, and our independent set algorithm has a runtime of O( (1/epsilon) log(1/epsilon)log^* n) rounds. For coloring, existing lower bounds imply that the dependencies on 1/epsilon and log n are best possible. For independent set, we prove that Omega(1/epsilon) rounds are necessary.
Both our algorithms make use of the tree decomposition of the input chordal graph. They iteratively peel off interval subgraphs, which are identified via the tree decomposition of the input graph, thereby partitioning the vertex set into O(log n) layers. For coloring, each interval graph is colored independently, which results in various coloring conflicts between the layers. These conflicts are then resolved in a separate phase, using the particular structure of our partitioning. For independent set, only the first O(log (1/epsilon)) layers are required as they already contain a large enough independent set. We develop a (1+epsilon)approximation maximum independent set algorithm for interval graphs, which we then apply to those layers.
This work raises the question as to how useful tree decompositions are for distributed computing.
BibTeX  Entry
@InProceedings{konrad_et_al:LIPIcs:2019:10965,
author = {Christian Konrad and Viktor Zamaraev},
title = {{Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs}},
booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
pages = {21:121:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771177},
ISSN = {18688969},
year = {2019},
volume = {138},
editor = {Peter Rossmanith and Pinar Heggernes and JoostPieter Katoen},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10965},
URN = {urn:nbn:de:0030drops109651},
doi = {10.4230/LIPIcs.MFCS.2019.21},
annote = {Keywords: local model, approximation algorithms, minimum vertex coloring, maximum independent set, chordal graphs}
}
20.08.2019
Keywords: 

local model, approximation algorithms, minimum vertex coloring, maximum independent set, chordal graphs 
Seminar: 

44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

Issue date: 

2019 
Date of publication: 

20.08.2019 