Even 1×n Edge-Matching and Jigsaw Puzzles are Really Hard
Even 1×n Edge-Matching and Jigsaw Puzzles are Really Hard
复制标题
即使是 1×n 边缘匹配和拼图游戏也非常困难
DOI：
10.2197/ipsjjip.25.682
复制
发表时间：
2016
影响因子：
--
通讯作者：
Anak Yodpinyanee
中科院分区：
文献类型：
--
作者：
Jeffrey Bosboom;E. Demaine;M. Demaine;Adam Hesterberg;Pasin Manurangsi;Anak Yodpinyanee
我们证明了旋转和放置$n$正方形瓷砖到一个$1 \times n$阵列，使相邻的瓷砖是兼容的计算棘手性-无论是平等的边缘颜色，在边缘匹配的拼图，或匹配的标签/口袋形状，在拼图。除了基本的NP-硬度，我们证明了它是NP-硬，甚至近似最大化的放置瓷砖（允许空白）的数量，同时满足非空白瓷砖之间的兼容性约束，在0.999999851的一个因素。(On另一方面，有一个简单的$1 \over 2$-近似值。）这是第一个（正确的）证明边缘匹配和拼图游戏的不可逼近性。沿着的方式，我们证明了NP-困难的区分，对于一个有向图的$n$节点，之间有一个哈密尔顿路径（长度$n-1$）和有至多$0.999999284（n-1）$的边缘，形成一个顶点不相交的道路联盟。我们使用这个间隙硬度和间隙保持减少，以建立类似的间隙硬度为1\times n$拼图和边缘匹配的难题。
We prove the computational intractability of rotating and placing $n$ square tiles into a $1 \times n$ array such that adjacent tiles are compatible--either equal edge colors, as in edge-matching puzzles, or matching tab/pocket shapes, as in jigsaw puzzles. Beyond basic NP-hardness, we prove that it is NP-hard even to approximately maximize the number of placed tiles (allowing blanks), while satisfying the compatibility constraint between nonblank tiles, within a factor of 0.9999999851. (On the other hand, there is an easy $1 \over 2$-approximation.) This is the first (correct) proof of inapproximability for edge-matching and jigsaw puzzles. Along the way, we prove NP-hardness of distinguishing, for a directed graph on $n$ nodes, between having a Hamiltonian path (length $n-1$) and having at most $0.999999284 (n-1)$ edges that form a vertex-disjoint union of paths. We use this gap hardness and gap-preserving reductions to establish similar gap hardness for $1 \times n$ jigsaw and edge-matching puzzles.