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(\frac{1}ε \log n)$ rounds, and our independent set algorithm has a runtime of $O(\frac{1}ε\log(\frac{1}ε)\log^* n)$ rounds. For coloring, existing lower bounds imply that the dependencies on $\frac{1}ε$ and $\log n$ are best possible. For independent set, we prove that $O(\frac{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 \frac{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. This work raises the question as to how useful tree decompositions are for distributed computing.