Distributed minimum vertex coloring and maximum independent set in chordal graphs.

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 O (1 ϵ log ⁡ n) rounds, and our independent set algorithm has a runtime of O (1 ϵ log ⁡ (1 ϵ) log ⁎ ⁡ n) rounds. For coloring, existing lower bounds imply that the dependencies on 1 ϵ and log ⁡ n are best possible. For independent set, we prove that Ω (1 ϵ) 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 O (log ⁡ 1 ϵ) 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. [ABSTRACT FROM AUTHOR]