Abstract

This document contains a list of open problems that Duc A. Hoang is interested in. It is also available in PDF format. Please get in touch if you have any idea/comment/question/update. You can find (probably more interesting) open problems from the following resources.

1 Preliminaries

Unless otherwise noted, all graphs are simple, undirected. We often denote by $P_{n},C_{n},K_{n},K_{m,n}$ the path, cycle, complete graph, complete bipartite graph on $n$ vertices, respectively. For two graphs $G,H$, the disjoint union of $G$ and $H$, denoted by $G+H$, is the graph with $V(G+H)=V(G)\cup V(H)$ and $E(G+H)=E(G)\cup E(H)$. For the terminology and notation not defined here, see the textbooks by Diestel [7] or West [14]. For more details on Combinatorial Reconfiguration (https://en.wikipedia.org/wiki/Reconfiguration), see the surveys [13, 12, 11, 5] and the wiki page https://reconf.wikidot.com/.

2 Reconfiguration of Independent Sets under Token Sliding

2.1 Definitions

The double-broom graph $D_{r,n,s}$ is the tree obtained from a path $P_{n}=v_{1}v_{2}\dots v_{n}$ by attaching $r$ leaves to $v_{1}$ and $s$ leaves to $v_{n}$, where $r,n,s$ are positive integers. Two independent sets $I,J$ are adjacent under Token Sliding $(\mathsf{TS})$ if there exists $u,v\in V(G)$ such that $I\setminus J=\{u\}$, $J\setminus I=\{v\}$, and $uv\in E(G)$. The Token Sliding problem asks whether there is a $\mathsf{TS}$-sequence between $I$ and $J$ in $G$, that is, a sequence of independent sets starting with $I$ and ending with $J$ where any two consecutive members are adjacent under $\mathsf{TS}$. For a fixed positive integer $k$, the graph $\mathsf{TS}_{k}(G)$ contains all size-$k$ independent sets as its vertices/nodes, and two nodes are joined by an edge if their corresponding independent sets are adjacent under $\mathsf{TS}$. A graph $G$ is called a $\mathsf{TS}_{k}$-graph if there exists a graph $H$ such that $G$ and $\mathsf{TS}_{k}(H)$ are isomorphic.

2.2 Conjecture/Question

Open Problem 1.

What is the complexity of Token Sliding on outerplanar graphs? And more generally, on series-parallel graphs ($\equiv$ graphs of treewidth at most two)?

Open Problem 2.

Let $G$ be a graph. What are necessary and sufficient conditions for $G$ such that $\mathsf{TS}_{2}(G)$ is acyclic?

Conjecture 3.

Let $G$ be a forest. Then $\mathsf{TS}_{k}(G)$ is a forest if and only if $G$ is $\{2K_{2}+(k-2)K_{1},D_{2,2,2}+(k-2)K_{1},D_{2,4,2}+(k-3)K_{1}\}$-free, for some integer $k\geq 4$.

2.3 Background/Motivation

Independent Set Reconfiguration (ISR) is one of the most well-studied problems in the Combinatorial Reconfiguration [12, 5]. Among several variants of ISR, Token Sliding is of particular interest. One of the main reasons is that in Token Sliding one often needs to deal with the situation where a token must make “detours” by “moving away” (and then moving back later) to allow some other token to move [6]. Alternatively, this can be seen as a kind of “bottleneck effect” [3] where a token may not be able to “reach” some vertices which are “far apart” from all tokens because some tokens “block the way”.

Our motivation for Open Problem 1 comes from the following two results that both appeared in 2014.

Theorem 4([15]).

There exists a constant $c$ such that Token Sliding (and two other variants of ISR) is $\mathtt{PSPACE}$-complete on graphs of bandwidth at most $c$.

Indeed, since a graph of bandwidth at most $c$ also has pathwidth and treewidth at most $c$, Theorem 4 holds for graphs of pathwidth/treewidth at most $c$. Moreover, for $c=1$,

Theorem 5([6]).

Token Sliding is in $\mathtt{P}$ on trees.

Naturally, on graphs of treewidth at most $c$, one may ask what the value of $c$ that separates “hard” from “easy” is. Toward answering this question, a first step is probably to consider $c=2$.

Our motivation for Open Problem 2 and Conjecture 3 comes from [1, 2]. In [1], the authors initiated the study of $\mathsf{TS}_{k}(G)$ from a purely graph-theoretic viewpoint. They continued their study in [2] focusing on those that are acyclic. Open Problem 2 involves characterizing general graphs, which seems to be quite challenging and a first step may be to consider well-known graph classes. Toward this direction, in [2], the authors proved a forbidden induced subgraph characterization of a tree $G$ satisfying that $\mathsf{TS}_{k}(G)$ is acyclic where $k\in\{2,3\}$ and Conjecture 3, if true, will provide a complete analysis of which trees having acyclic $\mathsf{TS}_{k}$-graphs.

3 Reconfiguring $k$-Path Vertex Covers on Trees under Token Sliding

3.1 Definitions

For a fixed integer $k\geq 2$, a $k$-path vertex cover of a graph $G$ is a vertex subset $I$ such that any path on $k$ vertices contains at least one member from $I$. Two $k$-path vertex covers are adjacent under Token Sliding ($\mathsf{TS}$) if there exists $u,v\in V(G)$ such that $I\setminus J=\{u\}$, $J\setminus I=\{v\}$, and $uv\in E(G)$. The $k$-Path Vertex Cover Reconfiguration under Token Sliding ($k$-PVCR-TS) problem asks if there is a $\mathsf{TS}$-sequence between two given $k$-path vertex covers $I$ and $J$ in $G$, that is, a sequence of $k$-path vertex covers starting with $I$ and ending with $J$ where any two consecutive members are adjacent under $\mathsf{TS}$.

3.2 Conjecture/Question

Open Problem 6.

What is the complexity of $k$-PVCR-TS on bipartite graphs? Or more restrictedly, on trees?

3.3 Background/Motivation

The $k$-PVCR-TS problem was first introduced in [9]. The complexities of $k$-PVCR-TS and some other variants have been characterized in [9] for some graph classes, including planar and bounded bandwidth graphs, trees, paths, and cycles. However, $k$-PVCR-TS on trees remains open. Our motivation comes from an attempt in [10] to solve this problem for a subclass of trees called caterpillars (i.e., trees obtained by attaching leaves to a central path). Unlike the cases for independent sets, a token may have to make “detours” by “moving closer” (and then moving back later) to allow some other tokens to move.

4 Recoloring under Token Swapping

4.1 Definitions

For a fixed integer $k\geq 1$, a proper $k$-coloring $\alpha$ of a graph $G$ is a function $\alpha:V(G)\to\{1,2,\dots,k\}$ such that for any edge $uv\in E(G)$ we have $\alpha(u)\neq\alpha(v)$. If $G$ has a proper $k$-coloring, we say that it is $k$-colorable. Two proper $k$-colorings $\alpha,\beta$ are adjacent under Token Swapping if there exist $u,v\in V(G)$ such that $\alpha(u)=\beta(v)$, $\alpha(v)=\beta(u)$, $\alpha(w)=\beta(w)$ for any $w\in V(G)-\{u,v\}$, and $uv\in E(G)$. The $k$-Recoloring under Token Swapping ($k$-RTS) problem asks if there is a sequence of adjacent proper $k$-colorings of $G$ under Token Swapping between two given proper $k$-colorings $\alpha,\beta$. The graph $\mathcal{C}_{k}^{RTS}(G)$ takes all proper $k$-colorings of $G$ as its nodes and their adjacency are defined under Token Swapping.

4.2 Conjecture/Question

Open Problem 7.

What is the complexity of $k$-RTS on trees for some fixed $k\geq 3$?

Open Problem 8.

What is the smallest value of $k$ such that $\mathcal{C}_{k}^{RTS}(G)$ is connected for some given graph $G$?

Open Problem 9.

What are necessary and sufficient conditions for a $k$-colorable graph $G$ such that $\mathcal{C}_{k+1}^{RTS}(G)$ is connected?

4.3 Background/Motivation

The $k$-RTS problem lies between two of the most well-studied problems in Combinatorial Reconfiguration: Token Swapping [16] and Vertex Recoloring [4]. (See [12, 11] for more details.) RTS was first proposed in [8] where the authors claimed that RTS remains $\mathtt{PSPACE}$-complete on planar graphs and can be solved in polynomial time on paths ($k=3$) and cographs (any $k$). Up to present, their results have not yet been published. The goal of our proposed open problems is to obtain a better understanding on the similarities and differences between $\mathcal{C}_{k}^{RTS}(G)$ and the well-stuided graph $\mathcal{C}_{k}(G)$—the graph whose nodes are proper $k$-colorings of $G$ and two nodes are adjacent if one can be obtained from the other by recoloring exactly one vertex.

References

• [1] D. Avis and D. A. Hoang (2022) On Reconfiguration Graph of Independent Sets under Token Sliding. arXiv preprint. External Links: 2203.16861 Cited by: §2.3.
• [2] D. Avis and D. A. Hoang (2023) A Note On Acyclic Token Sliding Reconfiguration Graphs of Independent Sets. arXiv preprint. External Links: 2301.00317 Cited by: §2.3.
• [3] V. Bartier, N. Bousquet, and A. E. Mouawad (2022) Galactic Token Sliding. In Proceedings of ESA 2022, S. Chechik, G. Navarro, E. Rotenberg, and G. Herman (Eds.), LIPIcs, Vol. 244, pp. 15:1–15:14. External Links: Document, 2204.05549 Cited by: §2.3.
• [4] P. S. Bonsma and L. Cereceda (2007) Finding Paths Between Graph Colourings: PSPACE-Completeness and Superpolynomial Distances. In Proceedings of MFCS 2007, LNCS, Vol. 4708, pp. 738–749. External Links: Document Cited by: §4.3.
• [5] N. Bousquet, A. E. Mouawad, N. Nishimura, and S. Siebertz (2022) A survey on the parameterized complexity of the independent set and (connected) dominating set reconfiguration problems. arXiv preprint. External Links: 2204.10526 Cited by: §1, §2.3.
• [6] E. D. Demaine, M. L. Demaine, E. Fox-Epstein, D. A. Hoang, T. Ito, H. Ono, Y. Otachi, R. Uehara, and T. Yamada (2015) Linear-Time Algorithm for Sliding Tokens on Trees. Theoretical Computer Science 600, pp. 132–142. External Links: Document, 1406.6576 Cited by: §2.3, Theorem 5.
• [7] R. Diestel (2017) Graph theory. 5th edition, Graduate Texts in Mathematics, Vol. 173, Springer. External Links: Document Cited by: §1.
• [8] D. Fischer and J. Fuchs (2019) Color reconfiguration with token swapping. External Links: Link Cited by: §4.3.
• [9] D. A. Hoang, A. Suzuki, and T. Yagita (2022) Reconfiguring $k$-Path Vertex Covers. IEICE Transactions on Information and Systems E105-D (7), pp. 1258–1272. External Links: Document, 1911.03026 Cited by: §3.3.
• [10] D. A. Hoang (2022) TS-Reconfiguration of $k$-Path Vertex Covers in Caterpillars for $k\geq 4$. arXiv preprint. External Links: 2203.11667 Cited by: §3.3.
• [11] C.M. Mynhardt and S. Nasserasr (2019) Reconfiguration of colourings and dominating sets in graphs. In 50 years of Combinatorics, Graph Theory, and Computing, F. Chung, R. Graham, F. Hoffman, R. C. Mullin, L. Hogben, and D. B. West (Eds.), pp. 171–191. External Links: Document, 2003.05956 Cited by: §1, §4.3.
• [12] N. Nishimura (2018) Introduction to reconfiguration. Algorithms 11 (4), pp. 52. External Links: Document Cited by: §1, §2.3, §4.3.
• [13] J. van den Heuvel (2013) The complexity of change. In Surveys in Combinatorics, London Mathematical Society Lecture Note Series, Vol. 409, pp. 127–160. External Links: Document, 1312.2816 Cited by: §1.
• [14] D. B. West (2001) Introduction to graph theory. 2nd edition, Prentice Hall. Cited by: §1.
• [15] M. Wrochna (2018) Reconfiguration in Bounded Bandwidth and Treedepth. Journal of Computer and System Sciences 93, pp. 1–10. External Links: Document, 1405.0847 Cited by: Theorem 4.
• [16] K. Yamanaka, E. D. Demaine, T. Ito, J. Kawahara, M. Kiyomi, Y. Okamoto, T. Saitoh, A. Suzuki, K. Uchizawa, and T. Uno (2015) Swapping Labeled Tokens on Graphs. Theoretical Computer Science 586, pp. 81–94. External Links: Document Cited by: §4.3.