License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2022.58
URN: urn:nbn:de:0030-drops-168567
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16856/
Ito, Takehiro ;
Iwamasa, Yuni ;
Kobayashi, Yasuaki ;
Nakahata, Yu ;
Otachi, Yota ;
Takahashi, Masahiro ;
Wasa, Kunihiro
Independent Set Reconfiguration on Directed Graphs
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.
BibTeX - Entry
@InProceedings{ito_et_al:LIPIcs.MFCS.2022.58,
author = {Ito, Takehiro and Iwamasa, Yuni and Kobayashi, Yasuaki and Nakahata, Yu and Otachi, Yota and Takahashi, Masahiro and Wasa, Kunihiro},
title = {{Independent Set Reconfiguration on Directed Graphs}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {58:1--58:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16856},
URN = {urn:nbn:de:0030-drops-168567},
doi = {10.4230/LIPIcs.MFCS.2022.58},
annote = {Keywords: Combinatorial reconfiguration, token sliding, directed graph, independent set, graph algorithm}
}
|
Keywords: |
|
Combinatorial reconfiguration, token sliding, directed graph, independent set, graph algorithm |
|
Collection: |
|
47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
22.08.2022 |
