Hardness of Token Swapping on Trees

Oswin Aichholzer • Erik Demaine • Matias Korman • Jayson Lynch • Anna Lubiw • Zuzana Masárová • Mikhail Rudoy • Virginia Vassilevska Williams • Nicole Wein

Token Swapping Problem

  • Given a graph
    • with one token per vertex
    • and a destination for each token
  • How many swaps along edges do we need?

Cayley Graph View

• Positions of tokens • Permutation in $S_n$
• Graph edge • Transposition (swap)
• Configuration space • Cayley graph
• Reconfiguration • Path in Cayley graph
https://commons.wikimedia.org/wiki/File:Symmetric_group_4;_Cayley_graph_1,2,6_(1-based).png

Connection to Bubble Sort

Path graph Sorting by swapping adjacent elements
Min number of swaps Number of inversions / cost of bubble sort

History

  • Studied in discrete mathematics, theoretical computer science, network engineering, robot motion planning, game theory
  • Cayley [1849] solved clique version
  • Knuth [1968] solved path version
  • Also solved for cycles, stars, brooms, bicliques
  • NP-complete [Amir & Porat 2015]
  • APX-complete with 4-approximation
    [Miltzow et al. 2016]
  • W[1]-hard with respect to number of swaps [Bonnet et al. 2018]

Token Swapping in Trees

History: Trees

  • Akers & Krishnamurthy [1989] first studied tree version as routing in proposed network topology
  • Three 2-approximation algorithms
    [Akers & Krishnamurthy 1989; Vaughan 1991; Yamanaka et al. 2015]
  • Family of algorithms (including past algorithms) cannot beat $4 \over 3$-approximation [Biniaz et al. 2019]
  • OPEN: NP-hard?
  • OPEN: Better approximation?

Our Results

  • Token swapping is NP-hard on trees
    • Also for parallel token swapping, where we can swap a matching in each round
  • Family of algorithms (including past algorithms) cannot beat 2-approximation

Happy Leaf Conjecture

  • Conjecture: [Vaughan 1991] Never need to swap a token that's already at destination leaf
  • Counterexample: [Biniaz et al. 2019]
    (smallest possible)
  • Any algorithm satisfying conjecture cannot beat $4 \over 3$-approximation [Biniaz et al. 2019]

Our Results

  • Token swapping is NP-hard on trees
    • Also for parallel token swapping, where we can swap a matching in each round
  • Algorithms that stay within 1 of shortest path cannot beat 2-approximation