Improved Hardness-Of-Approximation for Token-Swapping

Our main result is the first hardness of approximation result for token swapping with an explicit approximation ratio of “reasonable” magnitude. Specifically, we show that it is NP-hard to obtain better than a $14/13$-approximation:

Our result is via a reduction from the label cover problem. We note that our result does not rely on the Unique Games Conjecture, and is instead a gap-preserving reduction from a regime of the label cover problem known to be NP-complete.

For 0/1-weighted token swapping, our next result explains the aforementioned gap in the literature by showing a large separation between the 0/1-weighted and unweighted versions. Specifically, we show that it is NP-hard to obtain better than an $(\ln n)$-approximation for 0/1-weighted token swapping:

Our reduction uses a completely different technique from our main result, and is a much simpler reduction, from the set cover problem. This is notable in comparison to the known reductions in the token swapping literature, which tend to be quite complicated [1, 8, 18, 9].

Our final two results are barrier results regarding the algorithm and analysis techniques that could possibly achieve better than the current best-known approximation ratio of 4 (for standard unweighted token swapping). All known token swapping algorithms have the natural property of local optimality: they never perform a swap that brings both tokens farther from their destinations.¹¹1We compare the notion of a locally optimal algorithm to that of an $\mathrm{\ell }$-straying algorithm, introduced in prior work on token swapping for trees [1]. These two notions are incomparable: a swap sequence can have either property without having the other. However, any algorithm that solves token swapping on general graphs must generate an $\mathrm{\Omega }(n)$-straying swap sequence: consider the example of a cycle where each token wants to shift over by 1. For this reason, we do not consider $\mathrm{\ell }$-straying algorithms for general graphs, and focus instead on locally optimal algorithms. We show that, strangely, this property must be violated to achieve any approximation ratio better than 4.

In our second barrier result, we show that a proof technique used by all known analyses of approximation algorithms for token swapping, cannot yield better than a 4-approximation. In particular, all known approximation algorithms for token swapping on general graphs and trees [18, 35, 2] use the following approach to bound the approximation factor. Given a Token Swapping instance $K$, consider the quantity $total(K)={\sum }_{t\in T}\text{dist}(f_1(t),f_2(t))$. We observe that $\frac{1}{2}total(K)\le OPT(K)$, as each swap moves at most two tokens closer to their destinations. Proofs of correctness for approximation algorithms then show that they yield swap sequences of length at most $c\cdot total(K)$, which implies that the given algorithm is a $2c$-approximation. A natural approach to obtaining a $(4-ϵ)$-approximation for token swapping on graphs, then, is to show that on any input an algorithm yields a swap sequence of length at most $c\cdot total(K)$, for some . Below, we show that this approach will not work.

The proof is given in the full version.

Lastly, in the full version we provide an alternative algorithm that gives a 4-approximation for token swapping (in addition to the known algorithm [18]). While the algorithm of [18] is an extension of the 2-approximation “happy swap algorithm” for trees [2], our algorithm is an extension of the 2-approximation “cycle algorithm” for trees [35].

Token swapping and its variants have been studied from many angles. Exponential-time algorithms and hardness under the Exponential Time Hypothesis (ETH) were studied in [18]. Parameterized complexity was studied in [9], where the authors show that token swapping is W[1]-hard when the parameter is the number of swaps, and show further hardness under ETH. Token swapping has also been studied on a variety of special classes of graphs including cycles [16], stars [21, 20], brooms [17, 8, 31], complete bipartite graphs [35], complete split graphs [36], and cliques [10] (dating back to Cayley in 1849). Colored token swapping has also been studied, where each token has a color and same-colored tokens are indistinguishable [18, 8, 9, 34, 34]. There are also several other models of token movement on graphs such as token sliding, token rotation, and token permutation (see e.g. [28]). See also the introductions of [8] and [1] for more details on the wealth of related work.

Our reduction maps a label cover instance $\mathrm{\Phi }=(X,Y,E,\mathrm{\Sigma },\mathrm{\Pi })$, where the base graph has degree $d$, to a token swapping instance $K(\mathrm{\Phi })=(G,T,f_1,f_2)$.

We construct $G$ by building a gadget $\text{Gad}(v)$ for each $v\in X\cup Y$ as follows. Our construction for $\text{Gad}(v)$ starts with a base vertex $\text{bas}(v)$. We add $d$ additional vertices adjacent to $\text{bas}(v)$, which we call assignment vertices (recall that $d$ is the degree in the label-cover instance). To each assignment vertex in $\text{Gad}(v)$ we identify a unique edge $(v,w)\in E$ (where $E$ is the label cover edge set) incident to $v$; we call this assignment vertex $\text{asg}(v,w)$. We then create $|\mathrm{\Sigma }|$ paths, each with $\text{bas}(v)$ as an endpoint. We call these paths label paths. If $v\in X$, then each label path in $\text{Gad}(v)$ contains $d-1$ edges; if $v\in Y$, then each label path in $\text{Gad}(v)$ contains $2d-1$ edges. To each label path in $\text{Gad}(v)$ we associate a unique $\sigma \in \mathrm{\Sigma }$, and denote this label path by $\text{lab}(v,\sigma )$.

If $v\in X$, then we call $\text{Gad}(v)$ a left gadget; otherwise, we call $\text{Gad}(v)$ a right gadget. We call an assignment vertex a left (resp. right) assignment vertex if it is in a left (resp. right) gadget. We denote the set of left gadgets by L and the set of right gadgets by R.

Whenever it is the case that the label pair $({\sigma }_x,{\sigma }_y)$ satisfies the constraint ${\mathrm{\Pi }}_{(x,y)}$, we add a path of $d$ edges connecting the endpoint of $\text{lab}(x,{\sigma }_x)$ opposite $\text{bas}(x)$ with the endpoint of $\text{lab}(y,{\sigma }_y)$ opposite $\text{bas}(y)$. We call such a path a satisfaction path, and denote it by $\text{sat}(x,{\sigma }_x,y,{\sigma }_y)$.

This gives our construction for $G$. An illustration of a left and right gadget connected by a satisfaction path given in Figure 1. We construct $f_1$ and $f_2$ as follows. For each $(x,y)\in E$, the tokens on $\text{asg}(x,y)$ and $\text{asg}(y,x)$ wish to swap positions with each other. That is, $f_2(f_1^{-1}(\text{asg}(x,y)))=\text{asg}(y,x)$, and $f_2(f_1^{-1}(\text{asg}(y,x)))=\text{asg}(x,y)$.

We will refer to such a token as an assignment token. We will call an assignment token $t$ where $f_1(t)$ is a left (resp. right) assignment vertex a left (resp. right) assignment token. For $t\in T$ that are not assignment tokens, $f_1(t)=f_2(t)$. That is, $t$ does not wish to move from its starting position.

The intuition behind the reduction is as follows: if there is a labelling $\lambda$ satisfying every constraint in $\mathrm{\Pi }$, then all the assignment tokens that start in $\text{Gad}(v)$ can move to their destination along the single label path associated with $\lambda (v)$. Then, any assignment token seeking to enter $\text{Gad}(v)$ can travel along this path, and will in the process swap with many of the assignment tokens leaving $\text{Gad}(v)$, bringing them closer to their destination. If, on the other hand, no good labelling exists, then having so many efficient swaps becomes impossible.

We prove the following lemma.

Given a label-cover instance $\mathrm{\Phi }$, the token swapping instance $K(\mathrm{\Phi })$ can be computed in polynomial time. We set $d$ to be a large constant and $\gamma$ a small constant, and the hardness result of Theorem 1 follows from Lemma 9. In Section 3.2, we briefly discuss the proof of the first half of Lemma 9 (completeness), with a proof given in the full version. In Section 3.3, we prove the second half (soundness).

Let $\mathrm{\Phi }$ be a label-cover instance as defined in Lemma 9 such that $OPT(\mathrm{\Phi })=1$. We prove the first half of Lemma 9 by providing a swap sequence for $K(\mathrm{\Phi })$ using $(\frac{13}{4}{d}^2+d)|X\cup Y|$ swaps. We describe the procedure in detail, and prove the first half of Lemma 9 in the full version.

In this section, we will prove the second half of Lemma 9: if , then $OPT(K(\mathrm{\Phi }))>\left(\frac{7-\gamma }{2}{d}^2-5d\right)|X\cup Y|$.

Let $\mathrm{\Phi }$ be a label-cover instance such that , and let $S_{OPT}$ denote the optimal sequence of swaps on $K(\mathrm{\Phi })$. For a token $t\in T$, consider the subsequence of $S_{OPT}$ in which $t$ is one of the tokens being swapped. This subsequence traces out a walk in $G$. Consider the path from $f_1(t)$ to $f_2(t)$ obtained by removing all the closed sub-walks from this walk. We denote this path $\text{Swap}(t)$.

We now partition the assignment tokens into two types: detour tokens and non-detour (assignment) tokens.

We will refer to all other assignment tokens as non-detour tokens. This allows us to introduce the following notation: $de{t}_L$ (resp. $de{t}_R$) is the number of detour tokens $t$ such that $f_1(t)$ is a left (resp. right) assignment vertex. We will denote by $Det$ the set of detour tokens, and $Ndet$ the set of non-detour tokens.

We obtain lower bounds on two quantities: $B_{sat}$, the number of swaps occurring within satisfaction paths, and $B_{Gad}$, the number of swaps occurring within gadgets.

Combining these inequalities proves the second half of Lemma 9.

We define the following property for swap sequences on a Token Swapping instance.

All known algorithms for token swapping on trees or on general graphs work by returning the length of a swap sequence that is locally optimal.

See 3 We construct a token swapping instance $K$ as follows. See Figure 2. Let $p$ and $q$ be parameters to be decided later. We can assume $p$ is even. We begin with a cycle $C^{out}$ of length $p\cdot q$. Starting with an arbitrary vertex, we label the vertices $v_0,\mathrm{\dots },v_{p\cdot q-1}$ in one direction (say, clockwise) around the cycle. We partition the vertices of $C^{out}$ into $p$ consecutive “segments”. For any $0\le i\le p-1$, the vertices $\{v_{iq},\mathrm{\dots },v_{iq+(q-1)}\}$ form the $i$-th segment. If $i$ is even, we call such a segment an even segment; else it is an odd segment. For any $j$ so that $v_j$ is in an even segment, the token starting on $v_j$ has target vertex $v_{j+2q}(modpq)$. If $v_j$ is in an odd segment, the token starting on $v_j$ has target vertex $v_{j-2q}(modpq)$. That is, each token in an even segment wants to move to the corresponding vertex in the next even segment in the clockwise direction, while each token in an odd segment wants to move to the next odd segment over in the counter-clockwise direction. For each $0\le j\le pq$, we add a path $P_j$ of $2q-2$ edges between $v_j$ and $v_{j+2q}$. All the vertices on this path (except the endpoints in $C^{out}$) wish to stay on their start vertices. We call these paths inner paths. We call the vertices in $C^{out}$ outer vertices, and all other vertices inner vertices. Tokens that begin on outer vertices (which also have destinations on outer vertices) we call outer tokens; other tokens are inner tokens. Outer tokens with start and target vertices in even segments we will call even tokens; other outer tokens we will call odd tokens. Note that each outer token begins on a vertex connected to its target vertex by an inner cycle. The outer cycle, together with a single inner cycle, is depicted in Figure 2.