In the Token Swapping problem we are given a graph with a token placed oneach vertex. Each token has exactly one destination vertex, and we try to moveall the tokens to their destinations, using the minimum number of swaps, i.e.,operations of exchanging the tokens on two adjacent vertices. As the mainresult of this paper, we show that Token Swapping is $W[1]$-hard parameterizedby the length $k$ of a shortest sequence of swaps. In fact, we prove that, forany computable function $f$, it cannot be solved in time $f(k)n^{o(k / \logk)}$ where $n$ is the number of vertices of the input graph, unless the ETHfails. This lower bound almost matches the trivial $n^{O(k)}$-time algorithm. We also consider two generalizations of the Token Swapping, namely ColoredToken Swapping (where the tokens have different colors and tokens of the samecolor are indistinguishable), and Subset Token Swapping (where each token has aset of possible destinations). To complement the hardness result, we prove thateven the most general variant, Subset Token Swapping, is FPT in nowhere-densegraph classes. Finally, we consider the complexities of all three problems in veryrestricted classes of graphs: graphs of bounded treewidth and diameter, stars,cliques, and paths, trying to identify the borderlines between polynomial andNP-hard cases.
展开▼
机译：在令牌交换问题中，我们给了一个图形，在每个顶点上都放置了一个令牌。每个令牌都只有一个目标顶点，我们尝试使用最少的交换次数（即在两个相邻顶点上交换令牌的操作）将所有令牌移至它们的目的地。作为本文的主要结果，我们证明了令牌交换是$ W [1] $-hard，由最短交换序列的长度$ k $来参数化。实际上，我们证明了，对于任何可计算函数$ f $，它都无法及时解决$ f（k）n ^ {o（k / \ logk）} $，其中$ n $是输入图的顶点数，除非ETH失败。这个下限几乎与琐碎的$ n ^ {O（k）} $-time算法匹配。我们还考虑了令牌交换的两种概括，即：ColoredToken Swapping（其中的令牌具有不同的颜色，并且相同颜色的令牌是无法区分的）和Subset Token Swapping（子集令牌交换）（每个令牌具有一组可能的目的地）。为了补充硬度结果，我们证明即使是最普遍的变体，子集代币交换，在无处密集图类中也是FPT。最后，我们在非常严格的图类中考虑了所有三个问题的复杂性：有界树宽和直径，星图，斜度和路径图，试图确定多项式和NP硬情况之间的边界。
展开▼
