A note regarding "Sliding Tokens on Block Graphs"

Updated: May 22, 2019

This page was partially generated using LaTeXML. The content of this page is maintained by Duc A. Hoang and also available in PDF format.

1 Introduction

In this note, we introduce a counter-example for Proposition 6 of  and the progress of resolving this issue. This example was provided by Mariana Teatini Ribeiro and Vinícius Fernandes dos Santos. This issue has also been announced in . (Duc A. Hoang (me) and Ryuhei Uehara are co-authors in both publications.)

2 The problem

Let $I,J$ be two given independent sets of a graph $G$. Imagine that the vertices of an independent set are viewed as tokens (coins). A token is allowed to move (or slide) from one vertex to one of its neighbors. The Sliding Token problem asks whether there exists a sequence of independent sets of $G$ starting from $I$ and ending with $J$ such that each intermediate member of the sequence is obtained from the previous one by moving a token according to the allowed rule. If such a sequence exists, we write $I\overset{G}{\leftrightsquigarrow}J$. In , we claimed that this problem is solvable in polynomial time when the input graph is a block graph—a graph whose blocks (i.e., maximal $2$-connected subgraphs) are cliques.

3 Proposition 6 and its counter-example

Let $I$ be an independent set of a graph $G$. Let $W\subseteq V(G)$ and assume that $I\cap W\neq\emptyset$. We say that a token $t$ placed at some vertex $u\in I\cap W$ is $(G,I,W)$-confined if for every $J$ such that $I\overset{G}{\leftrightsquigarrow}J$, $t$ is always placed at some vertex of $W$. In other words, $t$ can only be slid along edges of $G[W]$. Let $H$ be an induced subgraph of $G$. $H$ is called $(G,I)$-confined if $I\cap V(H)$ is a maximum independent set of $H$ and all tokens in $I\cap V(H)$ are $(G,I,V(H))$-confined.

Mariana Teatini Ribeiro and Vinícius Fernandes dos Santos showed us a counter-example of the following proposition

Proposition 1 ([1, Proposition 6]).

Let $I$ be an independent set of a block graph $G$. Let $w\in V(G)$. Assume that no block of $G$ containing $w$ is $(G,I)$-confined. If there exists some vertex $x\in N_{G}[w]\cap I$ such that the token $t_{x}$ placed at $x$ is $(G,I,N_{G}[w])$-confined, then $x$ is unique. Consequently, there must be some independent set $J$ such that $I\overset{G}{\leftrightsquigarrow}J$ and $N_{G}[w]\cap J=\{x\}$. Moreover, let $H$ be the graph obtained from $G$ by turning $N_{G}[w]$ into a clique, called $B_{w}$. Then $t_{x}$ is $(G,J,N_{G}[w])$-confined if and only if $B_{w}$ is $(H,J)$-confined.

The statement Moreover, let $H$ be the graph obtained from $G$ by turning $N_{G}[w]$ into a clique, called $B_{w}$. Then $t_{x}$ is $(G,J,N_{G}[w])$-confined if and only if $B_{w}$ is $(H,J)$-confined is indeed not correct.

Figure 1 illustrates a counter-example of this statement. Here, the block $B_{w}$ of $H$ (containing $t_{x}$) is $(H,J)$-confined but $t_{x}$ is not $(G,J,N_{G}[w])$-confined. The red arrows in Figure 1 describes a way of moving $t_{x}$ out of $N_{G}[w]$. (The numbers inside red circles indicate the order of performing the steps described by the red arrows.)