Publication:5916255

DOI10.1007/978-3-319-94776-1_36zbMath1436.68136arXiv1803.06074OpenAlexW2964327015MaRDI QIDQ5916255

Takehiro Ito, Vijay Subramanya, Akira Suzuki, Naomi Nishimura, Krishna Vaidyanathan, Tesshu Hanaka, Haruka Mizuta, Benjamin Moore

Publication date: 4 October 2018

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

Abstract: Subgraph reconfiguration is a family of problems focusing on the reachability of the solution space in which feasible solutions are subgraphs, represented either as sets of vertices or sets of edges, satisfying a prescribed graph structure property. Although there has been previous work that can be categorized as subgraph reconfiguration, most of the related results appear under the name of the property under consideration; for example, independent set, clique, and matching. In this paper, we systematically clarify the complexity status of subgraph reconfiguration with respect to graph structure properties.

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

zbMATH Keywords

graph algorithmcombinatorial reconfiguration

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of rerouting shortest paths
• Complexity of independent set reconfigurability problems
• On the parameterized complexity of reconfiguration problems
• On the complexity of reconfiguration problems
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• Token jumping in minor-closed classes
• Reconfiguration in bounded bandwidth and tree-depth
• Introduction to reconfiguration
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• The complexity of change
• Degree-Constrained Subgraph Reconfiguration is in P
• Reconfiguration of Cliques in a Graph
• Reconfiguring spanning and induced subgraphs

Related Items (11)

Reconfiguration of regular induced subgraphs ⋮ Reconfiguring (non-spanning) arborescences ⋮ Reconfiguration of time-respecting arborescences ⋮ Unnamed Item ⋮ Reconfiguring directed trees in a digraph ⋮ Reconfiguration of Spanning Trees with Many or Few Leaves ⋮ Reconfiguring spanning and induced subgraphs ⋮ Reasons to fall (more) in love with combinatorial reconfiguration ⋮ Reconfiguration of Minimum Steiner Trees via Vertex Exchanges ⋮ Reconfiguration of connected graph partitions via recombination ⋮ Introduction to reconfiguration

This page was built for publication: Reconfiguring spanning and induced subgraphs