Reconfiguring Independent Sets on Interval Graphs

DOI10.4230/LIPICS.MFCS.2021.23MaRDI QIDQ6168437zbMATH OpenOpenAlexFDO

Authors Marcin Briański, Stefan Felsner, Piotr Micek

Publication date 8 August 2023

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

zbMATH Keywords

independent setsinterval graphsreconfiguration

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: We study reconfiguration of independent sets in interval graphs under the token sliding rule. We show that if two independent sets of size $k$ are reconfigurable in an $n$-vertex interval graph, then there is a reconfiguration sequence of length $mathcalO(kcdot{n}^2)$. We also provide a construction in which the shortest reconfiguration sequence is of length $Omega(k^{2}cdotn)$. As a counterpart to these results, we also establish that $extsfIndependentSetReconfiguration$ is PSPACE-hard on incomparability graphs, of which interval graphs are a special case.

Recommendations

• Independent set reconfiguration in cographs
• Independent set reconfiguration in cographs and their generalizations
• The complexity of independent set reconfiguration on bipartite graphs
• The complexity of independent set reconfiguration on bipartite graphs
• Reconfiguring independent sets in claw-free graphs
• Distributed independent sets in interval and segment intersection graphs
• On reconfiguration graphs of independent sets under token sliding
• Finding hidden independent sets in interval graphs
• Finding hidden independent sets in interval graphs
• Extremal independent set reconfiguration

Cited in

(10)

• Invitation to combinatorial reconfiguration
• Toggling independent sets of a path graph
• On the complexity of distance-\(d\) independent set reconfiguration
• On reconfiguration graphs of independent sets under token sliding
• Efficient non-isomorphic graph enumeration algorithms for several intersection graph classes
• On the complexity of distance-\(d\) independent set reconfiguration
• Changing induced subgraph isomorphisms under extended reconfiguration rules
• Changing induced subgraph isomorphisms under extended reconfiguration rules
• Coloring reconfiguration under color swapping
• Reachability of independent sets and vertex covers under extended reconfiguration rules

This page was built for publication: Reconfiguring Independent Sets on Interval Graphs

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