Distributed minimum vertex coloring and maximum independent set in chordal graphs

Konrad, Christian and Zamaraev, Viktor ORCID: 0000-0001-5755-4141 (2022) Distributed minimum vertex coloring and maximum independent set in chordal graphs. THEORETICAL COMPUTER SCIENCE, 922. pp. 486-502.

Text
full paper-rev.pdf - Author Accepted Manuscript
Download (579kB) | Preview

Official URL: http://dx.doi.org/10.1016/j.tcs.2022.04.047

Abstract

We give deterministic distributed (1+ϵ)-approximation algorithms for Minimum Vertex Coloring and Maximum Independent Set on chordal graphs in the LOCAL model. Our coloring algorithm runs in [Formula presented] rounds, and our independent set algorithm has a runtime of [Formula presented] rounds. For coloring, existing lower bounds imply that the dependencies on [Formula presented] and log⁡n are best possible. For independent set, we prove that [Formula presented] rounds are necessary. Both our algorithms make use of a 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 [Formula presented] layers are required as they already contain a large enough independent set. We develop a (1+ϵ)-approximation maximum independent set algorithm for interval graphs, which we then apply to those layers. While tree decompositions have only played a minor role in distributed computing, our work demonstrates their potential for designing efficient distributed algorithms.

Item Type:	Article
Uncontrolled Keywords:	Distributed algorithms, Maximum independent set, Minimum vertex coloring, Approximation algorithms, Chordal graphs
Divisions:	Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	31 May 2022 15:40
Last Modified:	18 Jan 2023 21:00
DOI:	10.1016/j.tcs.2022.04.047
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3155721