Independent set reconfiguration in cographs

DOI10.1007/978-3-319-12340-0_9zbMATH Open1417.05149arXiv1402.1587OpenAlexW1604387437MaRDI QIDQ2945182FDOQ2945182

Authors: Paul Bonsma 

Publication date: 9 September 2015

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Abstract: We study the following independent set reconfiguration problem, called TAR-Reachability: given two independent sets $I$ and $J$ of a graph $G$, both of size at least $k$, is it possible to transform $I$ into $J$ by adding and removing vertices one-by-one, while maintaining an independent set of size at least $k$ throughout? This problem is known to be PSPACE-hard in general. For the case that $G$ is a cograph (i.e. $P_4$-free graph) on $n$ vertices, we show that it can be solved in time $O(n^2)$, and that the length of a shortest reconfiguration sequence from $I$ to $J$ is bounded by $4n-2k$, if such a sequence exists. More generally, we show that if $X$ is a graph class for which (i) TAR-Reachability can be solved efficiently, (ii) maximum independent sets can be computed efficiently, and which satisfies a certain additional property, then the problem can be solved efficiently for any graph that can be obtained from a collection of graphs in $X$ using disjoint union and complete join operations. Chordal graphs are given as an example of such a class $X$.

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

Recommendations

• Independent set reconfiguration in cographs and their generalizations
• Complexity of independent set reconfigurability problems
• Reconfiguring independent sets in claw-free graphs
• Reconfiguration of Colorable Sets in Classes of Perfect Graphs
• Incremental optimization of independent sets under the reconfiguration framework

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cited In (15)

• Independent set reconfiguration in cographs and their generalizations
• Reconfiguring Independent Sets on Interval Graphs
• Independent-set reconfiguration thresholds of hereditary graph classes
• Independent-set reconfiguration thresholds of hereditary graph classes
• Toggling independent sets of a path graph
• Finding shortest paths between graph colourings
• Complexity of independent set reconfigurability problems
• Reconfiguration of cliques in a graph
• The complexity of independent set reconfiguration on bipartite graphs
• Reconfiguring independent sets in claw-free graphs
• Linear-time algorithm for sliding tokens on trees
• Incremental optimization of independent sets under the reconfiguration framework
• Reconfiguration of cliques in a graph
• The complexity of dominating set reconfiguration
• Extremal independent set reconfiguration

This page was built for publication: Independent set reconfiguration in cographs

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