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 Pn,Cn,Kn,Km,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)V(H) and E(G+H)=E(G)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 Dr,n,s is the tree obtained from a path Pn=v1v2vn by attaching r leaves to v1 and s leaves to vn, where r,n,s are positive integers. Two independent sets I,J are adjacent under Token Sliding (𝖳𝖲) if there exists u,vV(G) such that IJ={u}, JI={v}, and uvE(G). The Token Sliding problem asks whether there is a 𝖳𝖲-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 𝖳𝖲. For a fixed positive integer k, the graph 𝖳𝖲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 𝖳𝖲. A graph G is called a 𝖳𝖲k-graph if there exists a graph H such that G and 𝖳𝖲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 ( graphs of treewidth at most two)?

Open Problem 2.

Let G be a graph. What are necessary and sufficient conditions for G such that 𝖳𝖲2(G) is acyclic?

Conjecture 3.

Let G be a forest. Then 𝖳𝖲k(G) is a forest if and only if G is {2K2+(k-2)K1,D2,2,2+(k-2)K1,D2,4,2+(k-3)K1}-free, for some integer k4.

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 𝙿𝚂𝙿𝙰𝙲𝙴-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 𝙿 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 𝖳𝖲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 𝖳𝖲k(G) is acyclic where k{2,3} and Conjecture 3, if true, will provide a complete analysis of which trees having acyclic 𝖳𝖲k-graphs.

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

3.1 Definitions

For a fixed integer k2, 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 (𝖳𝖲) if there exists u,vV(G) such that IJ={u}, JI={v}, and uvE(G). The k-Path Vertex Cover Reconfiguration under Token Sliding (k-PVCR-TS) problem asks if there is a 𝖳𝖲-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 𝖳𝖲.

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 k1, a proper k-coloring α of a graph G is a function α:V(G){1,2,,k} such that for any edge uvE(G) we have α(u)α(v). If G has a proper k-coloring, we say that it is k-colorable. Two proper k-colorings α,β are adjacent under Token Swapping if there exist u,vV(G) such that α(u)=β(v), α(v)=β(u), α(w)=β(w) for any wV(G)-{u,v}, and uvE(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 α,β. The graph 𝒞kRTS(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 k3?

Open Problem 8.

What is the smallest value of k such that 𝒞kRTS(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 𝒞kRTS(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 𝙿𝚂𝙿𝙰𝙲𝙴-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 𝒞kRTS(G) and the well-stuided graph 𝒞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.