Token jumping in minor-closed classes

DOI10.1007/978-3-662-55751-8_12zbMATH Open1496.68263arXiv1706.09608OpenAlexW2725236087MaRDI QIDQ1679965FDOQ1679965

Authors: Nicolas Bousquet, Arnaud Mary, Aline Parreau 

Publication date: 22 November 2017

Abstract: Given two $k$-independent sets $I$ and $J$ of a graph $G$, one can ask if it is possible to transform the one into the other in such a way that, at any step, we replace one vertex of the current independent set by another while keeping the property of being independent. Deciding this problem, known as the Token Jumping (TJ) reconfiguration problem, is PSPACE-complete even on planar graphs. Ito et al. proved in 2014 that the problem is FPT parameterized by $k$ if the input graph is $K_{3,ell}$-free. We prove that the result of Ito et al. can be extended to any $K_{ell,ell}$-free graphs. In other words, if $G$ is a $K_{ell,ell}$-free graph, then it is possible to decide in FPT-time if $I$ can be transformed into $J$. As a by product, the TJ-reconfiguration problem is FPT in many well-known classes of graphs such as any minor-free class.

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

Recommendations

• scientific article; zbMATH DE number 475610
• scientific article; zbMATH DE number 4075052
• Elementary differences among jump classes
• scientific article; zbMATH DE number 860149
• Defining Jump Classes in the Degrees Below 0'
• Minimal universal and dense minor closed classes
• Double jumps of minimal degrees
• scientific article; zbMATH DE number 4095453
• On perfect switching classes
• On perfect switching classes

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Parameterized complexity, tractability and kernelization (68Q27)

Cited In (16)

• Fixed-parameter tractability of token jumping on planar graphs
• On girth and the parameterized complexity of token sliding and token jumping
• Token sliding on split graphs
• Token sliding on split graphs
• Reconfiguration on nowhere dense graph classes
• On finding short reconfiguration sequences between independent sets
• Parameterized complexity of independent set reconfiguration problems
• Introduction to reconfiguration
• Dominating sets reconfiguration under token sliding
• On finding short reconfiguration sequences between independent sets
• Title not available (Why is that?)
• Galactic token sliding
• The complexity of induced tree reconfiguration problems
• Incremental optimization of independent sets under the reconfiguration framework
• Reconfiguration of cliques in a graph
• The Perfect Matching Reconfiguration Problem

This page was built for publication: Token jumping in minor-closed classes

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