Activities per year
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 3dominating set) in each intermediate step is impossible. However, we provide efficient solutions when the intermediate sets are only required to be independent and 4dominating, 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 worstcase 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.
Original language  English 

Title of host publication  46th International Colloquium on Automata, Languages, and Programming, ICALP 2019 
Editors  Ioannis Chatzigiannakis, Christel Baier, Stefano Leonardi, Paola Flocchini 
Publisher  Schloss DagstuhlLeibnizZentrum für Informatik 
ISBN (Electronic)  9783959771092 
DOIs  
Publication status  Published  1 Jul 2019 
MoE publication type  A4 Article in a conference publication 
Event  International Colloquium on Automata, Languages and Programming  Patras, Greece Duration: 8 Jul 2019 → 12 Jul 2019 Conference number: 46 
Publication series
Name  Leibniz international proceedings in informatics 

Publisher  Schloss Dagstuhl LeibnizZentrum fur Informatik GmbH, Dagstuhl Publishing 
Volume  132 
ISSN (Print)  18688969 
Conference
Conference  International Colloquium on Automata, Languages and Programming 

Abbreviated title  ICALP 
Country/Territory  Greece 
City  Patras 
Period  08/07/2019 → 12/07/2019 
Fingerprint
Dive into the research topics of 'Distributed reconfiguration of maximal independent sets'. Together they form a unique fingerprint.Activities
 1 Visiting an external academic institution

Technion  Israel Institute of Technology
Mikael Rabie (Visiting researcher)
8 Apr 2018 → 17 Apr 2018Activity: Visiting an external institution types › Visiting an external academic institution