Reconfiguration of colorable sets in classes of perfect graphs
From MaRDI portal
Publication:2632018
Abstract: A set of vertices in a graph is c-colorable if the subgraph induced by the set has a proper c-coloring. In this paper, we study the problem of finding a step-by-step transformation (reconfiguration) between two c-colorable sets in the same graph. This problem generalizes the well-studied Independent Set Reconfiguration problem. As the first step toward a systematic understanding of the complexity of this general problem, we study the problem on classes of perfect graphs. We first focus on interval graphs and give a combinatorial characterization of the distance between two c-colorable sets. This gives a linear-time algorithm for finding an actual shortest reconfiguration sequence for interval graphs. Since interval graphs are exactly the graphs that are simultaneously chordal and co-comparability, we then complement the positive result by showing that even deciding reachability is PSPACE-complete for chordal graphs and for co-comparability graphs. The hardness for chordal graphs holds even for split graphs. We also consider the case where c is a fixed constant and show that in such a case the reachability problem is polynomial-time solvable for split graphs but still PSPACE-complete for co-comparability graphs. The complexity of this case for chordal graphs remains unsettled. As by-products, our positive results give the first polynomial-time solvable cases (split graphs and interval graphs) for Feedback Vertex Set Reconfiguration.
Recommendations
- Reconfiguration of Colorable Sets in Classes of Perfect Graphs
- scientific article; zbMATH DE number 7272506
- The coloring reconfiguration problem on specific graph classes
- scientific article; zbMATH DE number 1944138
- scientific article; zbMATH DE number 863472
- Reconfiguring \(k\)-colourings of complete bipartite graphs
- Colouring Some Classes of Perfect Graphs Robustly
- Perfect colorings of regular graphs
- Set colorings in perfect graphs.
- On the diameter of reconfiguration graphs for vertex colourings
Cites work
- A Characterization of Comparability Graphs and of Interval Graphs
- Algorithmic graph theory and perfect graphs
- Approximability of clique transversal in perfect graphs
- Complexity of independent set reconfigurability problems
- Efficient graph representations
- Finding a maximum-weight induced \(k\)-partite subgraph of an \(i\)-triangulated graph
- Generalized vertex covering in interval graphs
- Geometric algorithms and combinatorial optimization
- Incidence matrices and interval graphs
- Inductive \(k\)-independent graphs and \(c\)-colorable subgraphs in scheduling: a review
- Introduction to reconfiguration
- Linear-time algorithm for sliding tokens on trees
- Normal hypergraphs and the perfect graph conjecture
- On chain and antichain families of a partially ordered set
- On computing longest paths in small graph classes
- 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 for Max Colorable Induced Subgraph Problem on Perfect Graphs
- Parameterized algorithms for \((r,l)\)-partization
- Reconfiguration in bounded bandwidth and tree-depth
- Reconfiguring independent sets in claw-free graphs
- Some simplified NP-complete graph problems
- The complexity of change
- The complexity of generalized clique covering
- The complexity of independent set reconfiguration on bipartite graphs
- The complexity of rerouting shortest paths
- The maximum k-colorable subgraph problem for chordal graphs
- The strong perfect graph theorem
- Token sliding on chordal graphs
- Token sliding on split graphs
- Universal framework for wireless scheduling problems
Cited in
(8)- Reconfiguration of Colorable Sets in Classes of Perfect Graphs
- Transportation Problem Allowing Sending and Bringing Back
- On reconfigurability of target sets
- Token sliding on split graphs
- scientific article; zbMATH DE number 863472 (Why is no real title available?)
- Colouring Some Classes of Perfect Graphs Robustly
- Independent set reconfiguration in cographs and their generalizations
- On finding short reconfiguration sequences between independent sets
This page was built for publication: Reconfiguration of colorable sets in classes of perfect graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2632018)
