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 [1] 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 [2]. (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𝐺J. In [1], 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 WV(G) and assume that IW. We say that a token t placed at some vertex uIW is (G,I,W)-confined if for every J such that I𝐺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 IV(H) is a maximum independent set of H and all tokens in IV(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 wV(G). Assume that no block of G containing w is (G,I)-confined. If there exists some vertex xNG[w]I such that the token tx placed at x is (G,I,NG[w])-confined, then x is unique. Consequently, there must be some independent set J such that I𝐺J and NG[w]J={x}. Moreover, let H be the graph obtained from G by turning NG[w] into a clique, called Bw. Then tx is (G,J,NG[w])-confined if and only if Bw is (H,J)-confined.

The statement Moreover, let H be the graph obtained from G by turning NG[w] into a clique, called Bw. Then tx is (G,J,NG[w])-confined if and only if Bw is (H,J)-confined is indeed not correct.

Figure 1: A counter-example of Proposition 1.

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

4 Progress on resolving the issue

So far, we have not been able to resolve this issue.

References

  • [1] D. A. Hoang, E. Fox-Epstein and R. Uehara (2017) Sliding Tokens on Block Graphs. In Proceedings of WALCOM 2017, LNCS, Vol. 10167, pp. 460–471. External Links: Document Cited by: §1, §2, Proposition 1.
  • [2] D. A. Hoang, A. Khorramian and R. Uehara (2019) Shortest Reconfiguration Sequence for Sliding Tokens on Spiders. In Proceedings of CIAC 2019, P. Heggernes (Ed.), LNCS, Vol. 11485, pp. 262–273. External Links: Document Cited by: §1.