Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2411.16149 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908910817902592 |
|---|---|
| author | Banerjee, Niranka Engels, Christian Hoang, Duc A. |
| author_facet | Banerjee, Niranka Engels, Christian Hoang, Duc A. |
| contents | Reconfiguration problems involve determining whether two given configurations can be transformed into each other under specific rules. The Token Sliding problem asks whether, given two different set of tokens on vertices of a graph $G$, we can transform one into the other by sliding tokens step-by-step along edges of $G$ such that each resulting set of tokens forms an independent set in $G$. Recently, Ito et al. [MFCS 2022] introduced a directed variant of this problem. They showed that for general oriented graphs (i.e., graphs where no pair of vertices can have directed edges in both directions), the problem remains $\mathsf{PSPACE}$-complete, and is solvable in polynomial time on oriented trees.
In this paper, we further investigate the Token Sliding problem on various oriented graph classes. We show that the problem remains $\mathsf{PSPACE}$-complete for oriented split graphs, bipartite graphs and bounded treewidth graphs. Additionally, we present polynomial-time algorithms for solving the problem on oriented cycles and cographs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_16149 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Directed Token Sliding Banerjee, Niranka Engels, Christian Hoang, Duc A. Data Structures and Algorithms Reconfiguration problems involve determining whether two given configurations can be transformed into each other under specific rules. The Token Sliding problem asks whether, given two different set of tokens on vertices of a graph $G$, we can transform one into the other by sliding tokens step-by-step along edges of $G$ such that each resulting set of tokens forms an independent set in $G$. Recently, Ito et al. [MFCS 2022] introduced a directed variant of this problem. They showed that for general oriented graphs (i.e., graphs where no pair of vertices can have directed edges in both directions), the problem remains $\mathsf{PSPACE}$-complete, and is solvable in polynomial time on oriented trees. In this paper, we further investigate the Token Sliding problem on various oriented graph classes. We show that the problem remains $\mathsf{PSPACE}$-complete for oriented split graphs, bipartite graphs and bounded treewidth graphs. Additionally, we present polynomial-time algorithms for solving the problem on oriented cycles and cographs. |
| title | Directed Token Sliding |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2411.16149 |