Downloads: 0

Files in This Item:
This article will be available after a certain embargo period.
Please see the "Rights" information in item metadata display about embargo date.
Title: Feedback vertex set reconfiguration in planar graphs
Authors: Bousquet, Nicolas
Hommelsheim, Felix
Kobayashi, Yusuke
Mühlenthaler, Moritz
Suzuki, Akira
Author's alias: 小林, 佑輔
Keywords: Feedback vertex set
Combinatorial reconfiguration
Polynomial-time algorithm
Planar graph
Matroid parity
Issue Date: 10-Nov-2023
Publisher: Elsevier BV
Journal title: Theoretical Computer Science
Volume: 979
Thesis number: 114188
Abstract: We study the complexity of deciding whether for two given feedback vertex sets of a graph there is a step-by-step transformation between them, such that for each feedback vertex set in the transformation, the next one is obtained by exchanging a single vertex. We give a classification of the complexity of this question for planar graphs in terms of the maximum degree. We show that for planar graphs of maximum degree at most three the problem is tractable because there always exists a transformation, while it is PSPACE-complete when the maximum degree is at most four. The positive side of the classification extends to 𝘒₃, ₃ -minor-free graphs of maximum degree three. We then consider the Matroid Parity problem, which generalizes feedback vertex sets in graphs of maximum degree three as well as matchings and spanning trees in general graphs. Generalizing known results for the latter two we show that there always exists a transformation between any two non-maximum independent parity sets.
Rights: © 2023. This manuscript version is made available under the CC-BY-NC-ND 4.0 license
The full-text file will be made open to the public on 10 November 2025 in accordance with publisher's 'Terms and Conditions for Self-Archiving'.
This is not the published version. Please cite only the published version. この論文は出版社版でありません。引用の際には出版社版をご確認ご利用ください
DOI(Published Version): 10.1016/j.tcs.2023.114188
Appears in Collections:Journal Articles

Show full item record

Export to RefWorks

Export Format: 

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.