DROPS

Document

DOI: 10.4230/LIPIcs.FSTTCS.2016.34

Independent-Set Reconfiguration Thresholds of Hereditary Graph Classes

Authors: Mark de Berg, Bart M. P. Jansen, and Debankur Mukherjee

Published in: LIPIcs, Volume 65, 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)

Abstract

Traditionally, reconfiguration problems ask the question whether a given solution of an optimization problem can be transformed to a target solution in a sequence of small steps that preserve feasibility of the intermediate solutions. In this paper, rather than asking this question from an algorithmic perspective, we analyze the combinatorial structure behind it. We consider the problem of reconfiguring one independent set into another, using two different processes: (1) exchanging exactly k vertices in each step, or (2) removing or adding one vertex in each step while ensuring the intermediate sets contain at most k fewer vertices than the initial solution. We are interested in determining the minimum value of k for which this reconfiguration is possible, and bound these threshold values in terms of several structural graph parameters. For hereditary graph classes we identify structures that cause the reconfiguration threshold to be large.

Cite as

Mark de Berg, Bart M. P. Jansen, and Debankur Mukherjee. Independent-Set Reconfiguration Thresholds of Hereditary Graph Classes. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 65, pp. 34:1-34:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{deberg_et_al:LIPIcs.FSTTCS.2016.34,
  author =	{de Berg, Mark and Jansen, Bart M. P. and Mukherjee, Debankur},
  title =	{{Independent-Set Reconfiguration Thresholds of Hereditary Graph Classes}},
  booktitle =	{36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)},
  pages =	{34:1--34:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-027-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{65},
  editor =	{Lal, Akash and Akshay, S. and Saurabh, Saket and Sen, Sandeep},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2016.34},
  URN =		{urn:nbn:de:0030-drops-68694},
  doi =		{10.4230/LIPIcs.FSTTCS.2016.34},
  annote =	{Keywords: Reconfiguration, Independent set, Token Addition Removal, Token Sliding}
}

Search Results

Documents authored by Mukherjee, Debankur

Independent-Set Reconfiguration Thresholds of Hereditary Graph Classes

Abstract

Cite as

Thanks for your feedback!

Could not send message