ダウンロード数: 0
このアイテムのファイル:
このアイテムは一定期間後に公開されます。
公開日については,アイテム画面の「著作権等」でご確認ください。
公開日については,アイテム画面の「著作権等」でご確認ください。
タイトル: | Feedback vertex set reconfiguration in planar graphs |
著者: | Bousquet, Nicolas Hommelsheim, Felix Kobayashi, Yusuke Mühlenthaler, Moritz Suzuki, Akira |
著者名の別形: | 小林, 佑輔 |
キーワード: | Feedback vertex set Combinatorial reconfiguration Polynomial-time algorithm Planar graph Matroid parity |
発行日: | 10-Nov-2023 |
出版者: | Elsevier BV |
誌名: | Theoretical Computer Science |
巻: | 979 |
論文番号: | 114188 |
抄録: | 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. |
著作権等: | © 2023. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/ 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. この論文は出版社版でありません。引用の際には出版社版をご確認ご利用ください |
URI: | http://hdl.handle.net/2433/286140 |
DOI(出版社版): | 10.1016/j.tcs.2023.114188 |
出現コレクション: | 学術雑誌掲載論文等 |
このリポジトリに保管されているアイテムはすべて著作権により保護されています。