Reconfiguration of colorable sets in classes of perfect graphs

DOI10.1016/J.TCS.2018.11.024zbMATH Open1421.68135arXiv1802.06511OpenAlexW2903402681WikidataQ128820458 ScholiaQ128820458MaRDI QIDQ2632018FDOQ2632018

Authors: Takehiro Ito, Yota Otachi 

Publication date: 17 May 2019

Published in: Theoretical Computer Science (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

graph algorithmperfect graphcombinatorial reconfigurationcolorable set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15) Perfect graphs (05C17)

Cites Work

• Geometric algorithms and combinatorial optimization
• Normal hypergraphs and the perfect graph conjecture
• Efficient graph representations
• Algorithmic graph theory and perfect graphs
• Incidence matrices and interval graphs
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• On computing longest paths in small graph classes
• The strong perfect graph theorem
• Some simplified NP-complete graph problems
• A Characterization of Comparability Graphs and of Interval Graphs
• The complexity of change
• The maximum k-colorable subgraph problem for chordal graphs
• Generalized vertex covering in interval graphs
• The complexity of generalized clique covering
• Reconfiguring Independent Sets in Claw-Free Graphs
• Complexity of independent set reconfigurability problems
• On the parameterized complexity of reconfiguration problems
• On the complexity of reconfiguration problems
• On chain and antichain families of a partially ordered set
• Parameterized Algorithms for Max Colorable Induced Subgraph Problem on Perfect Graphs
• The complexity of rerouting shortest paths
• Token sliding on chordal graphs
• Linear-time algorithm for sliding tokens on trees
• Title not available (Why is that?)
• Parameterized Algorithms for (r,l)-Partization
• Approximability of clique transversal in perfect graphs
• Finding a maximum-weight induced \(k\)-partite subgraph of an \(i\)-triangulated graph
• Introduction to reconfiguration
• Title not available (Why is that?)
• Reconfiguration in bounded bandwidth and tree-depth
• Title not available (Why is that?)
• Inductive \(k\)-independent graphs and \(c\)-colorable subgraphs in scheduling: a review

Cited In (7)

• Token sliding on split graphs
• Colouring Some Classes of Perfect Graphs Robustly
• On reconfigurability of target sets
• On finding short reconfiguration sequences between independent sets
• Transportation Problem Allowing Sending and Bringing Back
• Title not available (Why is that?)
• Reconfiguration of Colorable Sets in Classes of Perfect Graphs

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)