Changing induced subgraph isomorphisms under extended reconfiguration rules

DOI10.1016/J.IC.2025.105367MaRDI QIDQ6884302zbMATH OpenFDO

Authors Tatsuhiro Suga, Akira Suzuki, Yuma Tamura, Xiao Zhou

Publication date 15 December 2025

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.IC.2025.105367

zbMATH Keywords

combinatorial reconfigurationextended reconfiguration ruleindependent set reconfigurationinduced subgraph isomorphismparameterized complexityPSPACE-completeness

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Cites work

• A birthday repetition theorem and complexity of approximating dense CSPs
• Changing induced subgraph isomorphisms under extended reconfiguration rules
• Combinatorial reconfiguration with answer set programming: algorithms, encodings, and empirical analysis
• Complexity of independent set reconfigurability problems
• From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
• scientific article; zbMATH DE number 3882470 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 7803580 (Why is no real title available?)
• Independent set reconfiguration in cographs and their generalizations
• Introduction to reconfiguration
• Linear-time algorithm for sliding tokens on trees
• Normal hypergraphs and the perfect graph conjecture. (Reprint)
• On the complexity of reconfiguration problems
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Reconfiguration in bounded bandwidth and tree-depth
• Reconfiguration of cliques in a graph
• Reconfiguration using generalized token jumping
• Reconfiguring independent sets in claw-free graphs
• Reconfiguring Independent Sets on Interval Graphs
• Reconfiguring spanning and induced subgraphs
• Relationships between nondeterministic and deterministic tape complexities
• The complexity of change
• The complexity of independent set reconfiguration on bipartite graphs
• The shortest path reconfiguration problem based on relaxation of reconfiguration rules
• The strong perfect graph theorem
• Token sliding on chordal graphs
• Token sliding on split graphs
• ZDD-based algorithmic framework for solving shortest reconfiguration problems

This page was built for publication: Changing induced subgraph isomorphisms under extended reconfiguration rules

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