| Summary: | The input to the token swapping problem is a graph with vertices $v_1, v_2,
\ldots, v_n$, and $n$ tokens with labels $1, 2, \ldots, n$, one on each vertex.
The goal is to get token $i$ to vertex $v_i$ for all $i= 1, \ldots, n$ using a
minimum number of swaps, where a swap exchanges the tokens on the endpoints of
an edge. We present some results about token swapping on a tree, also known as
"sorting with a transposition tree":
1. An optimum swap sequence may need to perform a swap on a leaf vertex that
has the correct token (a "happy leaf"), disproving a conjecture of Vaughan.
2. Any algorithm that fixes happy leaves -- as all known approximation
algorithms for the problem do -- has approximation factor at least $4/3$.
Furthermore, the two best-known 2-approximation algorithms have approximation
factor exactly 2.
3. A generalized problem -- weighted coloured token swapping -- is
NP-complete on trees, even when they are restricted to be subdivided stars, but
solvable in polynomial time on paths and stars. In this version, tokens and
vertices have colours, and colours have weights. The goal is to get every token
to a vertex of the same colour, and the cost of a swap is the sum of the
weights of the two tokens involved.
|
|---|