Swapping labeled tokens on graphs

Katsuhisa Yamanaka, Erik D. Demaine, Takehiro Ito, Jun Kawahara, Masashi Kiyomi, Yoshio Okamoto, Toshiki Saitoh, Akira Suzuki, Kei Uchizawa, Takeaki Uno

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

17 Citations (Scopus)


Consider a puzzle consisting of n tokens on an n-vertex graph, where each token has a distinct starting vertex and a distinct target vertex it wants to reach, and the only allowed transformation is to swap the tokens on adjacent vertices. We prove that every such puzzle is solvable in O(n2) token swaps, and thus focus on the problem of minimizing the number of token swaps to reach the target token placement. We give a polynomial-time 2-approximation algorithm for trees, and using this, obtain a polynomial-time 2α-approximation algorithm for graphs whose tree α-spanners can be computed in polynomial time. Finally, we show that the problem can be solved exactly in polynomial time on complete bipartite graphs.

Original languageEnglish
Title of host publicationFun with Algorithms - 7th International Conference, FUN 2014, Proceedings
PublisherSpringer Verlag
Number of pages12
ISBN (Print)9783319078892
Publication statusPublished - 2014
Event7th International Conference on Fun with Algorithms, FUN 2014 - Sicily, Italy
Duration: 2014 Jul 12014 Jul 3

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8496 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference7th International Conference on Fun with Algorithms, FUN 2014


Dive into the research topics of 'Swapping labeled tokens on graphs'. Together they form a unique fingerprint.

Cite this