Complexity of Token Swapping and Its Variants
Complexity of Token Swapping and Its Variants
复制标题
代币交换的复杂性及其变体
DOI：
10.1007/s00453-017-0387-0
复制
发表时间：
2016
期刊：
影响因子：
1.1
通讯作者：
Paweł Rzaͅżewski
中科院分区：
文献类型：
--
作者：
Édouard Bonnet;Tillmann Miltzow;Paweł Rzaͅżewski
在Token交换问题中，我们得到了一个图，每个顶点上都放置了一个令牌。每个令牌只有一个目的顶点，我们尝试使用最少的交换次数将所有令牌移动到它们的目的地，即在两个相邻顶点上交换令牌的操作。作为本文的主要结果，我们证明了Token交换是由最短交换序列的长度来参数化的。事实上，我们证明了，对于任何可计算的函数f，除非ETH失败，否则它不能在输入图的顶点数所在的时间内求解。这个下界几乎与平凡时间算法相匹配。我们还考虑了令牌交换的两个推广，即有色令牌交换(其中令牌具有颜色，并且相同颜色的令牌是不可区分的)和子集令牌交换(其中每个令牌具有一组可能的目的地)。为了补充困难的结果，我们证明了即使是最一般的变量，子集令牌交换，在无处密集的图类中也是FPT。最后，我们考虑了这三个问题在非常受限的图类中的复杂性：有界树宽和直径的图、星图、团图和路图，试图确定多项式和NP-困难情况之间的分界线。
In theToken Swappingproblem we are given a graph with a token placed on each vertex. Each token has exactly one destination vertex, and we try to move all the tokens to their destinations, using the minimum number of swaps, i.e., operations of exchanging the tokens on two adjacent vertices. As the main result of this paper, we show thatToken Swappingis-hard parameterized by the lengthkof a shortest sequence of swaps. In fact, we prove that, for any computable functionf, it cannot be solved in timewherenis the number of vertices of the input graph, unless the ETH fails. This lower bound almost matches the trivial-time algorithm. We also consider two generalizations of theToken Swapping, namelyColored Token Swapping(where the tokens have colors and tokens of the same color are indistinguishable), andSubset Token Swapping(where each token has a set of possible destinations). To complement the hardness result, we prove that even the most general variant,Subset Token Swapping, is FPT in nowhere-dense graph classes. Finally, we consider the complexities of all three problems in very restricted classes of graphs: graphs of bounded treewidth and diameter, stars, cliques, and paths, trying to identify the borderlines between polynomial and NP-hard cases.
在 STDk/3[k ;
DOI：
--
发表时间：
2008
期刊：
Discrete Mathematics 308
影响因子：
--
作者：
Y. Hiramine;C. Suetake;K. Akiyama C. Suetake
通讯作者：
K. Akiyama C. Suetake