1 Search Results for "Lomer, Kyle"

Document
DOI: 10.4230/LIPIcs.ISAAC.2020.44
On Girth and the Parameterized Complexity of Token Sliding and Token Jumping

Authors: Valentin Bartier, Nicolas Bousquet, Clément Dallard, Kyle Lomer, and Amer E. Mouawad

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract
In the Token Jumping problem we are given a graph G = (V,E) and two independent sets S and T of G, each of size k ≥ 1. The goal is to determine whether there exists a sequence of k-sized independent sets in G, 〈S_0, S_1, ..., S_𝓁〉, such that for every i, |S_i| = k, S_i is an independent set, S = S_0, S_𝓁 = T, and |S_i Δ S_i+1| = 2. In other words, if we view each independent set as a collection of tokens placed on a subset of the vertices of G, then the problem asks for a sequence of independent sets which transforms S to T by individual token jumps which maintain the independence of the sets. This problem is known to be PSPACE-complete on very restricted graph classes, e.g., planar bounded degree graphs and graphs of bounded bandwidth. A closely related problem is the Token Sliding problem, where instead of allowing a token to jump to any vertex of the graph we instead require that a token slides along an edge of the graph. Token Sliding is also known to be PSPACE-complete on the aforementioned graph classes. We investigate the parameterized complexity of both problems on several graph classes, focusing on the effect of excluding certain cycles from the input graph. In particular, we show that both Token Sliding and Token Jumping are fixed-parameter tractable on C_4-free bipartite graphs when parameterized by k. For Token Jumping, we in fact show that the problem admits a polynomial kernel on {C_3,C_4}-free graphs. In the case of Token Sliding, we also show that the problem admits a polynomial kernel on bipartite graphs of bounded degree. We believe both of these results to be of independent interest. We complement these positive results by showing that, for any constant p ≥ 4, both problems are W[1]-hard on {C_4, ..., C_p}-free graphs and Token Sliding remains W[1]-hard even on bipartite graphs.
Cite as

Valentin Bartier, Nicolas Bousquet, Clément Dallard, Kyle Lomer, and Amer E. Mouawad. On Girth and the Parameterized Complexity of Token Sliding and Token Jumping. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 44:1-44:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bartier_et_al:LIPIcs.ISAAC.2020.44,
  author =	{Bartier, Valentin and Bousquet, Nicolas and Dallard, Cl\'{e}ment and Lomer, Kyle and Mouawad, Amer E.},
  title =	{{On Girth and the Parameterized Complexity of Token Sliding and Token Jumping}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{44:1--44:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.44},
  URN =		{urn:nbn:de:0030-drops-133886},
  doi =		{10.4230/LIPIcs.ISAAC.2020.44},
  annote =	{Keywords: Combinatorial reconfiguration, Independent Set, Token Jumping, Token Sliding, Parameterized Complexity}
}
  • Refine by Author
  • 1 Bartier, Valentin
  • 1 Bousquet, Nicolas
  • 1 Dallard, Clément
  • 1 Lomer, Kyle
  • 1 Mouawad, Amer E.

  • Refine by Classification
  • 1 Mathematics of computing → Combinatoric problems
  • 1 Mathematics of computing → Graph algorithms
  • 1 Mathematics of computing → Paths and connectivity problems

  • Refine by Keyword
  • 1 Combinatorial reconfiguration
  • 1 Independent Set
  • 1 Parameterized Complexity
  • 1 Token Jumping
  • 1 Token Sliding

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2020

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact