Independent-set reconfiguration thresholds of hereditary graph classes

DOI10.1016/J.DAM.2018.05.029MaRDI QIDQ1801058zbMATH OpenOpenAlexDBLPWikidataFDO

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

Publication date 26 October 2018

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

Full work available at URL https://arxiv.org/abs/1610.03766, https://drops.dagstuhl.de/opus/volltexte/2016/6869/

zbMATH Keywords

independent setreconfigurationtoken addition removaltoken sliding

Mathematics Subject Classification ID

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

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.

Recommendations

• Independent-set reconfiguration thresholds of hereditary graph classes
• Extremal independent set reconfiguration
• Independent set reconfiguration in cographs
• Parameterized complexity of independent set reconfiguration problems
• Incremental optimization of independent sets under the reconfiguration framework

Cites work

• scientific article; zbMATH DE number 3862930 (Why is no real title available?)
• A partial k-arboretum of graphs with bounded treewidth
• Bounds on isoperimetric values of trees
• Complexity of independent set reconfigurability problems
• Fast Mixing of Parallel Glauber Dynamics and Low-Delay CSMA Scheduling
• Graph theory
• Hitting time asymptotics for hard-core interactions on grids
• Independent set reconfiguration in cographs
• Introduction to reconfiguration
• Kernel bounds for path and cycle problems
• Linear-time algorithm for sliding tokens on trees
• Loss networks
• Metastability of hard-core dynamics on bipartite graphs
• Multi-color pebble motion on graphs
• Obstruction set isolation for the gate matrix layout problem
• On the complexity of reconfiguration problems
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Parameterized algorithms
• Pushing squares around
• Reconfiguration in bounded bandwidth and tree-depth
• Reconfigurations in Graphs and Grids
• Reconfiguring independent sets in claw-free graphs
• Reducibility among combinatorial problems
• Sliding token on bipartite permutation graphs
• Some Theorems on Abstract Graphs
• The complexity of change
• The complexity of independent set reconfiguration on bipartite graphs

Cited in

(4)

• Extremal independent set reconfiguration
• On easy and hard hereditary classes of graphs with respect to the independent set problem
• Independent-set reconfiguration thresholds of hereditary graph classes
• Can local optimality be used for efficient data reduction?

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1801058)