1 Search Results for "Morgan, Adir"


Document
Algorithms for the Minimum Dominating Set Problem in Bounded Arboricity Graphs: Simpler, Faster, and Combinatorial

Authors: Adir Morgan, Shay Solomon, and Nicole Wein

Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)


Abstract
We revisit the minimum dominating set problem on graphs with arboricity bounded by α. In the (standard) centralized setting, Bansal and Umboh [Bansal and Umboh, 2017] gave an O(α)-approximation LP rounding algorithm, which also translates into a near-linear time algorithm using general-purpose approximation results for explicit mixed packing and covering or pure covering LPs [Koufogiannakis and Young, 2014; Young, 2014; Allen-Zhu and Orecchia, 2019; Quanrud, 2020]. Moreover, [Bansal and Umboh, 2017] showed that it is NP-hard to achieve an asymptotic improvement for the approximation factor. On the other hand, the previous two non-LP-based algorithms, by Lenzen and Wattenhofer [Christoph Lenzen and Roger Wattenhofer, 2010], and Jones et al. [Jones et al., 2013], achieve an approximation factor of O(α²) in linear time. There is a similar situation in the distributed setting: While there is an O(log² n)-round LP-based O(α)-approximation algorithm implied in [Kuhn et al., 2006], the best non-LP-based algorithm by Lenzen and Wattenhofer [Christoph Lenzen and Roger Wattenhofer, 2010] is an implementation of their centralized algorithm, providing an O(α²)-approximation within O(log n) rounds. We address the questions of whether one can achieve an O(α)-approximation algorithm that is elementary, i.e., not based on any LP-based methods, either in the centralized setting or in the distributed setting. We resolve both questions in the affirmative, and en route achieve algorithms that are faster than the state-of-the-art LP-based algorithms. Our contribution is two-fold: 1) In the centralized setting, we provide a surprisingly simple combinatorial algorithm that is asymptotically optimal in terms of both approximation factor and running time: an O(α)-approximation in linear time. The previous state-of-the-art O(α)-approximation algorithms are (1) LP-based, (2) more complicated, and (3) have super-linear running time. 2) Based on our centralized algorithm, we design a distributed combinatorial O(α)-approximation algorithm in the CONGEST model that runs in O(αlog n) rounds with high probability. Not only does this result provide the first nontrivial non-LP-based distributed o(α²)-approximation algorithm for this problem, it also outperforms the best LP-based distributed algorithm for a wide range of parameters.

Cite as

Adir Morgan, Shay Solomon, and Nicole Wein. Algorithms for the Minimum Dominating Set Problem in Bounded Arboricity Graphs: Simpler, Faster, and Combinatorial. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 33:1-33:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{morgan_et_al:LIPIcs.DISC.2021.33,
  author =	{Morgan, Adir and Solomon, Shay and Wein, Nicole},
  title =	{{Algorithms for the Minimum Dominating Set Problem in Bounded Arboricity Graphs: Simpler, Faster, and Combinatorial}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{33:1--33:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.33},
  URN =		{urn:nbn:de:0030-drops-148353},
  doi =		{10.4230/LIPIcs.DISC.2021.33},
  annote =	{Keywords: Graph Algorithms, Dominating Set, Bounded Arboricity, Linear time algorithms}
}
  • Refine by Author
  • 1 Morgan, Adir
  • 1 Solomon, Shay
  • 1 Wein, Nicole

  • Refine by Classification
  • 1 Theory of computation → Distributed algorithms
  • 1 Theory of computation → Graph algorithms analysis

  • Refine by Keyword
  • 1 Bounded Arboricity
  • 1 Dominating Set
  • 1 Graph Algorithms
  • 1 Linear time algorithms

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2021

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail