Independent-set reconfiguration thresholds of hereditary graph classes

DOI10.1016/J.DAM.2018.05.029zbMath1398.05155DBLPjournals/dam/BergJM18arXiv1610.03766OpenAlexW2538002713WikidataQ60123385 ScholiaQ60123385MaRDI QIDQ1801058

Bart M. P. Jansen, Debankur Mukherjee, Mark T. de Berg

Publication date: 26 October 2018

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1610.03766

zbMATH Keywords

independent setreconfigurationtoken addition removaltoken sliding

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Hitting time asymptotics for hard-core interactions on grids
• Kernel bounds for path and cycle problems
• Complexity of independent set reconfigurability problems
• Linear-time algorithm for sliding tokens on trees
• On the parameterized complexity of reconfiguration problems
• On the complexity of reconfiguration problems
• Bounds on isoperimetric values of trees
• Loss networks
• A partial k-arboretum of graphs with bounded treewidth
• Obstruction set isolation for the gate matrix layout problem
• Reconfiguration in bounded bandwidth and tree-depth
• Reconfiguration on sparse graphs
• Multi-color pebble motion on graphs
• Metastability of hard-core dynamics on bipartite graphs
• Introduction to reconfiguration
• Pushing squares around
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• The complexity of change
• Independent Set Reconfiguration in Cographs
• Fast Mixing of Parallel Glauber Dynamics and Low-Delay CSMA Scheduling
• Reconfiguring Independent Sets in Claw-Free Graphs
• Sliding Token on Bipartite Permutation Graphs
• Reducibility among Combinatorial Problems
• Parameterized Algorithms
• Some Theorems on Abstract Graphs
• Reconfigurations in Graphs and Grids

Related Items (1)

Can local optimality be used for efficient data reduction?

This page was built for publication: Independent-set reconfiguration thresholds of hereditary graph classes