Fixed-parameter tractability of token jumping on planar graphs

DOI10.1007/978-3-319-13075-0_17MaRDI QIDQ2942629zbMATH OpenOpenAlexFDO

Authors Takehiro Ito, Marcin Kamiński, Hirotaka Ono

Publication date 11 September 2015

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1406.6567

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27)

Abstract: Suppose that we are given two independent sets $I_0$ and $I_r$ of a graph such that $|I_0|=|I_r|$, and imagine that a token is placed on each vertex in $I_0$. The token jumping problem is to determine whether there exists a sequence of independent sets which transforms $I_0$ into $I_r$ so that each independent set in the sequence results from the previous one by moving exactly one token to another vertex. This problem is known to be PSPACE-complete even for planar graphs of maximum degree three, and W[1]-hard for general graphs when parameterized by the number of tokens. In this paper, we present a fixed-parameter algorithm for the token jumping problem on planar graphs, where the parameter is only the number of tokens. Furthermore, the algorithm can be modified so that it finds a shortest sequence for a yes-instance. The same scheme of the algorithms can be applied to a wider class of graphs, $K_{3,t}$-free graphs for any fixed integer $tge3$, and it yields fixed-parameter algorithms.

Recommendations

• On the Parameterized Complexity for Token Jumping on Graphs
• Parameterized complexity of independent set reconfiguration problems
• On girth and the parameterized complexity of token sliding and token jumping
• Token jumping in minor-closed classes
• Polynomial-time algorithm for sliding tokens on trees

Cited in

(19)

• Reconfiguration on nowhere dense graph classes
• On girth and the parameterized complexity of token sliding and token jumping
• Token sliding on split graphs
• Parameterized complexity of independent set reconfiguration problems
• Introduction to reconfiguration
• Token sliding on split graphs
• Shortest reconfiguration paths in the solution space of Boolean formulas
• On the Parameterized Complexity for Token Jumping on Graphs
• Incremental optimization of independent sets under the reconfiguration framework
• scientific article; zbMATH DE number 7765402 (Why is no real title available?)
• Galactic token sliding
• On finding short reconfiguration sequences between independent sets
• On finding short reconfiguration sequences between independent sets
• Galactic token sliding
• Independent set reconfiguration in H-free graphs
• A survey on the parameterized complexity of reconfiguration problems
• Independent set reconfiguration on directed graphs
• A simple quadratic kernel for token jumping on surfaces
• The tape reconfiguration problem and its consequences for dominating set reconfiguration

This page was built for publication: Fixed-parameter tractability of token jumping on planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2942629)