DROPS

Document

Brief Announcement

DOI: 10.4230/LIPIcs.DISC.2025.54

Brief Announcement: Faster CONGEST Approximation Algorithms for Maximum Weighted Independent Set in Sparse Graphs

Authors: Salwa Faour and Fabian Kuhn

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract

The maximum independent set problem is a classic optimization problem in graph theory that has also been studied quite intensively in the distributed setting. Although the problem is hard to approximate within reasonable factors in general, there are good approximation algorithms known for several sparse graph families. In the present paper, we consider deterministic distributed CONGEST algorithms for the weighted version of the problem in trees and graphs of bounded arboricity (i.e., hereditary sparse graphs). For trees, we prove that the task of deterministically computing a (1-ε)-approximate solution to the maximum weight independent set (MWIS) problem has a tight Θ(log^*(n) / ε) complexity. The lower bound already holds on unweighted oriented paths. On the upper bound side, we show that the bound can be achieved even in unrooted trees. For graphs G = (V,E) of arboricity β > 1, we give two algorithms. If the sum of all node weights is w(V), we show that for any ε > 0, an independent set of weight at least (1-ε)⋅(w(V))/(4β) can be computed in O(log²(β/ε)/ε + log^* n) rounds. This result is obtained by a direct application of the local rounding framework of Faour, Ghaffari, Grunau, Kuhn, and Rozhoň [SODA ‘23]. We further show that for any ε > 0, an independent set of weight at least (1-ε)⋅(w(V))/(2β+1) can be computed in O(log³(β)⋅log(1/ε)/ε² ⋅log n) rounds. For ε = ω(1/√{β}), this significantly improves on a recent result of Gil [OPODIS ‘23], who showed that a 1/⌊(2+ε)β⌋-approximation to the MWIS problem can be computed in O(β/ε⋅log n) rounds. As an intermediate step to our result, we design an algorithm to compute an independent set of total weight at least (1-ε)⋅∑_{v ∈ V}(w(v))/(deg(v)+1) in time O(log³(Δ)⋅log(1/ε)/ε + log^* n), where Δ is the maximum degree of the graph.

Cite as

Salwa Faour and Fabian Kuhn. Brief Announcement: Faster CONGEST Approximation Algorithms for Maximum Weighted Independent Set in Sparse Graphs. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 54:1-54:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{faour_et_al:LIPIcs.DISC.2025.54,
  author =	{Faour, Salwa and Kuhn, Fabian},
  title =	{{Brief Announcement: Faster CONGEST Approximation Algorithms for Maximum Weighted Independent Set in Sparse Graphs}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{54:1--54:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.54},
  URN =		{urn:nbn:de:0030-drops-248704},
  doi =		{10.4230/LIPIcs.DISC.2025.54},
  annote =	{Keywords: CONGEST model, weighted independent set, approximation, trees, arboricity}
}

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}
}

Document

DOI: 10.4230/LIPIcs.OPODIS.2020.29

Approximating Bipartite Minimum Vertex Cover in the CONGEST Model

Authors: Salwa Faour and Fabian Kuhn

Published in: LIPIcs, Volume 184, 24th International Conference on Principles of Distributed Systems (OPODIS 2020)

Abstract

We give efficient distributed algorithms for the minimum vertex cover problem in bipartite graphs in the CONGEST model. From Kőnig’s theorem, it is well known that in bipartite graphs the size of a minimum vertex cover is equal to the size of a maximum matching. We first show that together with an existing O(nlog n)-round algorithm for computing a maximum matching, the constructive proof of Kőnig’s theorem directly leads to a deterministic O(nlog n)-round CONGEST algorithm for computing a minimum vertex cover. We then show that by adapting the construction, we can also convert an approximate maximum matching into an approximate minimum vertex cover. Given a (1-δ)-approximate matching for some δ > 1, we show that a (1+O(δ))-approximate vertex cover can be computed in time O (D+poly((log n)/δ)), where D is the diameter of the graph. When combining with known graph clustering techniques, for any ε ∈ (0,1], this leads to a poly((log n)/ε)-time deterministic and also to a slightly faster and simpler randomized O((log n)/ε³)-round CONGEST algorithm for computing a (1+ε)-approximate vertex cover in bipartite graphs. For constant ε, the randomized time complexity matches the Ω(log n) lower bound for computing a (1+ε)-approximate vertex cover in bipartite graphs even in the LOCAL model. Our results are also in contrast to the situation in general graphs, where it is known that computing an optimal vertex cover requires Ω̃(n²) rounds in the CONGEST model and where it is not even known how to compute any (2-ε)-approximation in time o(n²).

Cite as

Salwa Faour and Fabian Kuhn. Approximating Bipartite Minimum Vertex Cover in the CONGEST Model. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 29:1-29:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{faour_et_al:LIPIcs.OPODIS.2020.29,
  author =	{Faour, Salwa and Kuhn, Fabian},
  title =	{{Approximating Bipartite Minimum Vertex Cover in the CONGEST Model}},
  booktitle =	{24th International Conference on Principles of Distributed Systems (OPODIS 2020)},
  pages =	{29:1--29:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-176-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{184},
  editor =	{Bramas, Quentin and Oshman, Rotem and Romano, Paolo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2020.29},
  URN =		{urn:nbn:de:0030-drops-135149},
  doi =		{10.4230/LIPIcs.OPODIS.2020.29},
  annote =	{Keywords: distributed vertex cover, distributed graph algorithms, distributed optimization, bipartite vertex cover}
}

Search Results

Documents authored by Faour, Salwa

Brief Announcement: Faster CONGEST Approximation Algorithms for Maximum Weighted Independent Set in Sparse Graphs

Abstract

Cite as

Distributed CONGEST Approximation of Weighted Vertex Covers and Matchings

Abstract

Cite as

Approximating Bipartite Minimum Vertex Cover in the CONGEST Model

Abstract

Cite as

Thanks for your feedback!

Could not send message