Konrad, Christian and Zamaraev, Viktor 
ORCID: 0000-0001-5755-4141
(2018)
Distributed Minimum Vertex Coloring and Maximum Independent Set in
Chordal Graphs.
.
|
Text
1805.04544v1.pdf - Submitted version Download (596kB) | Preview |
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(\frac{1}{\epsilon} \log n)$ rounds, and our independent set algorithm has a runtime of $O(\frac{1}{\epsilon}\log(\frac{1}{\epsilon})\log^* n)$ rounds. For coloring, existing lower bounds imply that the dependencies on $\frac{1}{\epsilon}$ and $\log n$ are best possible. For independent set, we prove that $O(\frac{1}{\epsilon})$ 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}{\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.
| Item Type: | Conference or Workshop Item (Unspecified) |
|---|---|
| Uncontrolled Keywords: | cs.DS, cs.DS |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 07 Sep 2020 08:11 |
| Last Modified: | 18 Jan 2023 23:35 |
| DOI: | 10.4230/LIPIcs.MFCS.2019.21 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3100219 |
Dimensions
Dimensions
