Complexity of Token Swapping and Its Variants

2016/07/26 by Édouard Bonnet, Bonnet, Édouard, Tillmann Miltzow +3 · 1 voice · 5 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #Biology #Computational Complexity (cs.CC) #Computational biology #Computer network #Computer science #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Genome Rearrangement Algorithms #Security token #cs.CC #cs.DM #cs.DS #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1607.07676

published in Algorithmica 80(9), 2656-2682 (Springer Science+Business Media) · 23 pages, 7 Figures

openalex publication_date 2017/10/20 · arxiv created 2018/01/05 · arxiv updated 2018/01/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04

Abstract

In the Token Swapping problem we are given a graph with a token placed on each vertex. Each token has exactly one destination vertex, and we try to move all the tokens to their destinations, using the minimum number of swaps, i.e., operations of exchanging the tokens on two adjacent vertices. As the main result of this paper, we show that Token Swapping is W[1] -hard parameterized by the length k of a shortest sequence of swaps. In fact, we prove that, for any computable function f, it cannot be solved in time f(k)n^{o(k / log k)} where n is the number of vertices of the input graph, unless the ETH fails. This lower bound almost matches the trivial n^O(k) -time algorithm. We also consider two generalizations of the Token Swapping, namely Colored Token Swapping (where the tokens have colors and tokens of the same color are indistinguishable), and Subset Token Swapping (where each token has a set of possible destinations). To complement the hardness result, we prove that even the most general variant, Subset Token Swapping, is FPT in nowhere-dense graph classes. Finally, we consider the complexities of all three problems in very restricted classes of graphs: graphs of bounded treewidth and diameter, stars, cliques, and paths, trying to identify the borderlines between polynomial and NP-hard cases.

Citations

• Clustering to minimize the maximum intercluster distance
• Which Problems Have Strongly Exponential Complexity?
• On a Problem of Formal Logic
• Deciding first-order properties of nowhere dense graphs
• The NP-Completeness of Some Edge-Partition Problems
• The complexity of completing partial Latin squares
• A Combinatorial Problem in Geometry
• Graph puzzles, homotopy, and the alternating group

Cited by

• Coloring Reconfiguration under Color Swapping
• Dependence-Driven, Scalable Quantum Circuit Mapping with Affine Abstractions
• Diameter Bounds for Friends-and-Strangers Graphs
• Settling Weighted Token Swapping up to Algorithmic Barriers
• Universal Solvability for Robot Motion Planning on Graphs

Discussions

• Lemma 2 in this paper https://link.springer.com/article/10.1007/s00453-017-0387-0 is that "Directed Triangle Decomposition is NP-complete, even if the input digraph $H = (V, A)$ is Eulerian and has no [stackexchange, 0 points]

Related

• Hardness of Token Swapping on Trees
• Improved Hardness-of-Approximation for Token Swapping
• Swapping Colored Tokens on Graphs
• Settling Weighted Token Swapping up to Algorithmic Barriers
• Sequentially Swapping Tokens: Further on Graph Classes