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.ISAAC.2020.37
URN: urn:nbn:de:0030-drops-133812
URL: https://drops.dagstuhl.de/opus/volltexte/2020/13381/
Go to the corresponding LIPIcs Volume Portal


Bousquet, Nicolas ; Joffard, Alice ; Ouvrard, Paul

Linear Transformations Between Dominating Sets in the TAR-Model

pdf-format:
LIPIcs-ISAAC-2020-37.pdf (0.6 MB)


Abstract

Given a graph G and an integer k, a token addition and removal (TAR for short) reconfiguration sequence between two dominating sets D_s and D_t of size at most k is a sequence S = āŸØ Dā‚€ = D_s, Dā‚ ā€¦, D_š“ = D_t āŸ© of dominating sets of G such that any two consecutive dominating sets differ by the addition or deletion of one vertex, and no dominating set has size bigger than k.
We first improve a result of Haas and Seyffarth [R. Haas and K. Seyffarth, 2017], by showing that if k = Ī“(G)+Ī±(G)-1 (where Ī“(G) is the maximum size of a minimal dominating set and Ī±(G) the maximum size of an independent set), then there exists a linear TAR reconfiguration sequence between any pair of dominating sets.
We then improve these results on several graph classes by showing that the same holds for K_š“-minor free graph as long as k ā‰„ Ī“(G)+O(š“ āˆš(log š“)) and for planar graphs whenever k ā‰„ Ī“(G)+3. Finally, we show that if k = Ī“(G)+tw(G)+1, then there also exists a linear transformation between any pair of dominating sets.

BibTeX - Entry

@InProceedings{bousquet_et_al:LIPIcs:2020:13381,
  author =	{Nicolas Bousquet and Alice Joffard and Paul Ouvrard},
  title =	{{Linear Transformations Between Dominating Sets in the TAR-Model}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{37:1--37:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Yixin Cao and Siu-Wing Cheng and Minming Li},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/13381},
  URN =		{urn:nbn:de:0030-drops-133812},
  doi =		{10.4230/LIPIcs.ISAAC.2020.37},
  annote =	{Keywords: reconfiguration, dominating sets, addition removal, connectivity, diameter, minor, treewidth}
}

Keywords: reconfiguration, dominating sets, addition removal, connectivity, diameter, minor, treewidth
Collection: 31st International Symposium on Algorithms and Computation (ISAAC 2020)
Issue Date: 2020
Date of publication: 04.12.2020


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