Feedback vertex set reconfiguration in planar graphs

DOI10.1016/j.tcs.2023.114188MaRDI QIDQ6057837

Nicolas Bousquet, Yusuke Kobayashi, Moritz Mühlenthaler, Felix Hommelsheim, Akira Suzuki

Publication date: 26 October 2023

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

zbMATH Keywords

polynomial-time algorithmplanar graphmatroid parityfeedback vertex setcombinatorial reconfiguration

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Complexity of independent set reconfigurability problems
• On the complexity of reconfiguration problems
• On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three
• Matroid matching and some applications
• Token sliding on chordal graphs
• Shortest reconfiguration of matchings
• Introduction to reconfiguration
• A simple PTAS for weighted matroid matching on strongly base orderable matroids
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• The complexity of change
• On feedback vertex sets and nonseparating independent sets in cubic graphs
• The Complexity of Independent Set Reconfiguration on Bipartite Graphs
• Parameterized Complexity of Graph Constraint Logic
• Reconfiguration of Spanning Trees with Many or Few Leaves
• Reconfiguration of spanning trees with degree constraints or diameter constraints

This page was built for publication: Feedback vertex set reconfiguration in planar graphs