Science-advisor
REGISTER info/FAQ
Login
username
password
     
forgot password?
register here
 
Research articles
  search articles
  reviews guidelines
  reviews
  articles index
My Pages
my alerts
  my messages
  my reviews
  my favorites
 
 
Stat
Members: 3667
Articles: 2'599'751
Articles rated: 2609

09 February 2025
 
  » arxiv » 1605.0442

 Article overview



Token Sliding on Chordal Graphs
Marthe Bonamy ; Nicolas Bousquet ;
Date 2 May 2016
AbstractLet I be an independent set of a graph G. Imagine that a token is located on any vertex of I. We can now move the tokens of I along the edges of the graph as long as the set of tokens still defines an independent set of G. Given two independent sets I and J, the Token Sliding problem consists in deciding whether there exists a sequence of independent sets which transforms I into J so that every pair of consecutive independent sets of the sequence can be obtained via a token move. This problem is known to be PSPACE-complete even on planar graphs.
In 2014, Demaine et al. asked whether the Token Sliding reconfiguration problem is polynomial time solvable on interval graphs and more generally in chordal graphs. Yamada and Uehara showed in 2016 that a polynomial time transformation can be found in proper interval graphs.
In this paper, we answer the first question of Demaine et al. and generalize the result of Yamada and Uehara by showing that we can decide in polynomial time whether two independent sets of an interval graph are in the same connected component. Moveover, we answer similar questions by showing that: (i) determining if there exists a token sliding transformation between every pair of k-independent sets in an interval graph can be decided in polynomial time; (ii) deciding this problem becomes co-NP-hard and even co-W[2]-hard (parameterized by the size of the independent set) on split graphs, a sub-class of chordal graphs.
Source arXiv, 1605.0442
Services Forum | Review | PDF | Favorites   
 
Visitor rating: did you like this article? no 1   2   3   4   5   yes

No review found.
 Did you like this article?

This article or document is ...
important:
of broad interest:
readable:
new:
correct:
Global appreciation:

  Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.






ScienXe.org
» my Online CV
» Free

home  |  contact  |  terms of use  |  sitemap
Copyright © 2005-2025 - Scimetrica