DROPS

Document

DOI: 10.4230/LIPIcs.DISC.2023.22

List Defective Colorings: Distributed Algorithms and Applications

Authors: Marc Fuchs and Fabian Kuhn

Published in: LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023)

Abstract

The distributed coloring problem is at the core of the area of distributed graph algorithms and it is a problem that has seen tremendous progress over the last few years. Much of the remarkable recent progress on deterministic distributed coloring algorithms is based on two main tools: a) defective colorings in which every node of a given color can have a limited number of neighbors of the same color and b) list coloring, a natural generalization of the standard coloring problem that naturally appears when colorings are computed in different stages and one has to extend a previously computed partial coloring to a full coloring. In this paper, we introduce list defective colorings, which can be seen as a generalization of these two coloring variants. Essentially, in a list defective coloring instance, each node v is given a list of colors x_{v,1},… ,x_{v,p} together with a list of defects d_{v,1},… ,d_{v,p} such that if v is colored with color x_{v, i}, it is allowed to have at most d_{v, i} neighbors with color x_{v, i}. We highlight the important role of list defective colorings by showing that faster list defective coloring algorithms would directly lead to faster deterministic (Δ+1)-coloring algorithms in the LOCAL model. Further, we extend a recent distributed list coloring algorithm by Maus and Tonoyan [DISC '20]. Slightly simplified, we show that if for each node v it holds that ∑_{i=1}^p (d_{v,i}+1)² > deg_G²(v)⋅ polylogΔ then this list defective coloring instance can be solved in a communication-efficient way in only O(logΔ) communication rounds. This leads to the first deterministic (Δ+1)-coloring algorithm in the standard CONGEST model with a time complexity of O(√{Δ}⋅ polylog Δ+log^* n), matching the best time complexity in the LOCAL model up to a polylogΔ factor.

Cite as

Marc Fuchs and Fabian Kuhn. List Defective Colorings: Distributed Algorithms and Applications. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 22:1-22:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{fuchs_et_al:LIPIcs.DISC.2023.22,
  author =	{Fuchs, Marc and Kuhn, Fabian},
  title =	{{List Defective Colorings: Distributed Algorithms and Applications}},
  booktitle =	{37th International Symposium on Distributed Computing (DISC 2023)},
  pages =	{22:1--22:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-301-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{281},
  editor =	{Oshman, Rotem},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.22},
  URN =		{urn:nbn:de:0030-drops-191484},
  doi =		{10.4230/LIPIcs.DISC.2023.22},
  annote =	{Keywords: distributed coloring, list coloring, defective coloring}
}

Document

DOI: 10.4230/LIPIcs.OPODIS.2021.17

Distributed CONGEST Approximation of Weighted Vertex Covers and Matchings

Authors: Salwa Faour, Marc Fuchs, and Fabian Kuhn

Published in: LIPIcs, Volume 217, 25th International Conference on Principles of Distributed Systems (OPODIS 2021)

Abstract

We provide CONGEST model algorithms for approximating the minimum weighted vertex cover and the maximum weighted matching problem. For bipartite graphs, we show that a (1+ε)-approximate weighted vertex cover can be computed deterministically in poly((log n)/ε) rounds. This generalizes a corresponding result for the unweighted vertex cover problem shown in [Faour, Kuhn; OPODIS '20]. Moreover, we show that in general weighted graph families that are closed under taking subgraphs and in which we can compute an independent set of weight at least λ⋅ w(V) (where w(V) denotes the total weight of all nodes) in polylogarithmic time in the CONGEST model, one can compute a (2-2λ +ε)-approximate weighted vertex cover in poly((log n)/ε) rounds in the CONGEST model. Our result in particular implies that in graphs of arboricity a, one can compute a (2-1/a+ε)-approximate weighted vertex cover problem in poly((log n)/ε) rounds in the CONGEST model. For maximum weighted matchings, we show that a (1-ε)-approximate solution can be computed deterministically in time 2^{O(1/ε)}⋅ polylog n in the CONGEST model. We also provide a randomized algorithm that with arbitrarily good constant probability succeeds in computing a (1-ε)-approximate weighted matching in time 2^{O(1/ε)}⋅ polylog(Δ W)⋅ log^* n, where W denotes the ratio between the largest and the smallest edge weight. Our algorithm generalizes results of [Lotker, Patt-Shamir, Pettie; SPAA '08] and [Bar-Yehuda, Hillel, Ghaffari, Schwartzman; PODC '17], who gave 2^{O(1/ε)}⋅ log n and 2^{O(1/ε)}⋅ (logΔ)/(log logΔ)-round randomized approximations for the unweighted matching problem. Finally, we show that even in the LOCAL model and in bipartite graphs of degree ≤ 3, if ε < ε₀ for some constant ε₀ > 0, then computing a (1+ε)-approximation for the unweighted minimum vertex cover problem requires Ω((log n)/ε) rounds. This generalizes a result of [Göös, Suomela; DISC '12], who showed that computing a (1+ε₀)-approximation in such graphs requires Ω(log n) rounds.

Cite as

Salwa Faour, Marc Fuchs, and Fabian Kuhn. Distributed CONGEST Approximation of Weighted Vertex Covers and Matchings. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 17:1-17:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{faour_et_al:LIPIcs.OPODIS.2021.17,
  author =	{Faour, Salwa and Fuchs, Marc and Kuhn, Fabian},
  title =	{{Distributed CONGEST Approximation of Weighted Vertex Covers and Matchings}},
  booktitle =	{25th International Conference on Principles of Distributed Systems (OPODIS 2021)},
  pages =	{17:1--17:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-219-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{217},
  editor =	{Bramas, Quentin and Gramoli, Vincent and Milani, Alessia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2021.17},
  URN =		{urn:nbn:de:0030-drops-157928},
  doi =		{10.4230/LIPIcs.OPODIS.2021.17},
  annote =	{Keywords: distributed graph algorithms, minimum weighted vertex cover, maximum weighted matching, distributed optimization, CONGEST model}
}

Search Results

Documents authored by Fuchs, Marc

List Defective Colorings: Distributed Algorithms and Applications

Abstract

Cite as

Distributed CONGEST Approximation of Weighted Vertex Covers and Matchings

Abstract

Cite as

Thanks for your feedback!

Could not send message