License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2019.135
URN: urn:nbn:de:0030-drops-107111
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10711/
Go to the corresponding LIPIcs Volume Portal

Censor-Hillel, Keren ; Rabie, Mikaël

Distributed Reconfiguration of Maximal Independent Sets

pdf-format:
LIPIcs-ICALP-2019-135.pdf (0.5 MB)

Abstract

In this paper, we investigate a distributed maximal independent set (MIS) reconfiguration problem, in which there are two maximal independent sets for which every node is given its membership status, and the nodes need to communicate with their neighbors in order to find a reconfiguration schedule that switches from the first MIS to the second. Such a schedule is a list of independent sets that is restricted by forbidding two neighbors to change their membership status at the same step. In addition, these independent sets should provide some covering guarantee.
We show that obtaining an actual MIS (and even a 3-dominating set) in each intermediate step is impossible. However, we provide efficient solutions when the intermediate sets are only required to be independent and 4-dominating, which is almost always possible, as we fully characterize.
Consequently, our goal is to pin down the tradeoff between the possible length of the schedule and the number of communication rounds. We prove that a constant length schedule can be found in O(MIS+R32) rounds, where MIS is the complexity of finding an MIS in a worst-case graph and R32 is the complexity of finding a (3,2)-ruling set. For bounded degree graphs, this is O(log^*n) rounds and we show that it is necessary. On the other extreme, we show that with a constant number of rounds we can find a linear length schedule.

BibTeX - Entry

@InProceedings{censorhillel_et_al:LIPIcs:2019:10711,
  author =	{Keren Censor-Hillel and Mika{\"e}l Rabie},
  title =	{{Distributed Reconfiguration of Maximal Independent Sets}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{135:1--135:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10711},
  URN =		{urn:nbn:de:0030-drops-107111},
  doi =		{10.4230/LIPIcs.ICALP.2019.135},
  annote =	{Keywords: distributed graph algorithms, reconfiguration, maximal independent set}
}

Keywords: distributed graph algorithms, reconfiguration, maximal independent set
Collection: 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Issue Date: 2019
Date of publication: 04.07.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI