| アイテムタイプ |
会議発表論文 / Conference Paper(1) |
| 公開日 |
2024-04-10 |
| タイトル |
|
|
タイトル |
Independent Set Reconfiguration on Directed Graphs |
| 言語 |
|
|
言語 |
eng |
| キーワード |
|
|
主題Scheme |
Other |
|
主題 |
Combinatorial reconfiguration |
| キーワード |
|
|
主題Scheme |
Other |
|
主題 |
token sliding |
| キーワード |
|
|
主題Scheme |
Other |
|
主題 |
directed graph |
| キーワード |
|
|
主題Scheme |
Other |
|
主題 |
independent set |
| キーワード |
|
|
主題Scheme |
Other |
|
主題 |
graph algorithm |
| 資源タイプ |
|
|
資源タイプ |
conference paper |
| アクセス権 |
|
|
アクセス権 |
open access |
| 著者 |
Ito, Takehiro
Iwamasa, Yuni
Kobayashi, Yasuaki
中畑, 裕
Otachi, Yota
Takahashi, Masahiro
Wasa, Kunihiro
|
| 抄録 |
|
|
内容記述タイプ |
Abstract |
|
内容記述 |
Directed Token Sliding asks, given a directed graph and two sets of pairwise nonadjacent vertices, whether one can reach from one set to the other by repeatedly applying a local operation that exchanges a vertex in the current set with one of its out-neighbors, while keeping the nonadjacency. It can be seen as a reconfiguration process where a token is placed on each vertex in the current
set, and the local operation slides a token along an arc respecting its direction. Previously, such a problem was extensively studied on undirected graphs, where the edges have no directions and thus the local operation is symmetric. Directed Token Sliding is a generalization of its undirected variant since an undirected edge can be simulated by two arcs of opposite directions. In this paper, we initiate the algorithmic study of Directed Token Sliding. We first observe that the problem is PSPACE-complete even if we forbid parallel arcs in opposite directions and that the problem on directed acyclic graphs is NP-complete and W[1]-hard parameterized by the size of the sets in consideration. We then show our main result: a linear-time algorithm for the problem on directed graphs whose underlying undirected graphs are trees, which are called polytrees. Such a result is also known for the undirected variant of the problem on trees [Demaine et al. TCS 2015], but the techniques used here are quite different because of the asymmetric nature of the directed problem. We present a characterization of yes-instances based on the existence of a certain set of directed paths, and then derive simple equivalent conditions from it by some observations, which yield an efficient algorithm. For the polytree case, we also present a quadratic-time algorithm that
outputs, if the input is a yes-instance, one of the shortest reconfiguration sequences. |
| 書誌情報 |
en : 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
発行日 2022-08-22
|
| 会議情報 |
|
|
|
会議名 |
47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022) |
|
|
開始年 |
2022 |
|
|
開始月 |
08 |
|
|
開始日 |
22 |
|
|
終了年 |
2022 |
|
|
終了月 |
08 |
|
|
終了日 |
26 |
|
|
開催地 |
Vienna |
|
開催国 |
AUT |
| 出版者 |
|
|
出版者 |
Schloss Dagstuhl |
| ISSN |
|
|
収録物識別子タイプ |
EISSN |
|
収録物識別子 |
1868-8969 |
| 出版者版DOI |
|
|
関連タイプ |
isReplacedBy |
|
|
識別子タイプ |
DOI |
|
|
関連識別子 |
https://doi.org/10.4230/LIPIcs.MFCS.2022.58 |
| 出版者版URI |
|
|
関連タイプ |
isReplacedBy |
|
|
識別子タイプ |
URI |
|
|
関連識別子 |
https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.58 |
| 権利 |
|
|
権利情報Resource |
https://creativecommons.org/licenses/by/4.0/legalcode |
|
権利情報 |
$00A9 Takehiro Ito, Yuni Iwamasa, Yasuaki Kobayashi, Yu Nakahata, Yota Otachi, Masahiro Takahashi, and Kunihiro Wasa; licensed under Creative Commons License CC-BY 4.0 |
| 著者版フラグ |
|
|
出版タイプ |
NA |
