Complexity of Token Swapping and its Variants

Edouard Bonnet , Tillmann Miltzow , Paweł Rzążewski


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)no(k/logk) where n is the number of vertices of the input graph, unless the ETH fails. This lower bound almost matches the trivial nO(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.
Author Edouard Bonnet - [Middlesex University]
Edouard Bonnet,,
, Tillmann Miltzow - [Université libre de Bruxelles (ULB)]
Tillmann Miltzow,,
, Paweł Rzążewski (FMIS / DIPS)
Paweł Rzążewski,,
- Department of Information Processing Systems
Journal seriesAlgorithmica, ISSN 0178-4617, (A 25 pkt)
Issue year2018
Publication size in sheets0.65
Keywords in Polishsortowanie na grafie, złożoność obliczeniowa
Keywords in Englishtoken swapping, parameterized complexity
ASJC Classification2604 Applied Mathematics; 1706 Computer Science Applications; 1700 General Computer Science
Abstract in PolishW problemie sortowania na grafie dany jest graf o n wierzchołkach oraz n żetonów, z których każdy odpowiada innemu wierzchołkowi. Żetony leżą na wierzchołkach (niekoniecznie im odpowiadających). Naszym zadaniem jest doprowadzenie każdego żetonu to odpowiadającego mu wierzchołka przy użyciu minimalnej liczby zamian żetonów leżących na końcach krawędzi. W pracy pokazujemy, że problem jest W[1]-trudny ze względu na liczbę dozwolonych zamian. Ponadto pokazujemy, że problem pozostaje trudny nawet w ograniczonych klasach grafów. Rozważamy też jego pewne uogólnienia.
Languageen angielski
Score (nominal)25
ScoreMinisterial score = 25.0, 26-04-2019, ArticleFromJournal
Ministerial score (2013-2016) = 25.0, 11-03-2019, ArticleFromJournal
Publication indicators Scopus Citations = 0; WoS Citations = 0; Scopus SNIP (Source Normalised Impact per Paper): 2016 = 1.338; WoS Impact Factor: 2017 = 0.667 (2) - 2017=0.843 (5)
Citation count*
Share Share

Get link to the record

* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.