License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2017.16
URN: urn:nbn:de:0030-drops-70185
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7018/
Go to the corresponding LIPIcs Volume Portal

Bonnet, Édouard ; Miltzow, Tillmann ; Rzazewski, Pawel

Complexity of Token Swapping and its Variants

pdf-format:
LIPIcs-STACS-2017-16.pdf (0.7 MB)

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.

BibTeX - Entry

@InProceedings{bonnet_et_al:LIPIcs:2017:7018,
  author =	{{\'E}douard Bonnet and Tillmann Miltzow and Pawel Rzazewski},
  title =	{{Complexity of Token Swapping and its Variants}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{16:1--16:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Heribert Vollmer and Brigitte Vallée},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7018},
  URN =		{urn:nbn:de:0030-drops-70185},
  doi =		{10.4230/LIPIcs.STACS.2017.16},
  annote =	{Keywords: token swapping, parameterized complexity, NP-hardness, W[1]-hardness}
}

Keywords: token swapping, parameterized complexity, NP-hardness, W[1]-hardness
Collection: 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)
Issue Date: 2017
Date of publication: 06.03.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI