zbMATH — the first resource for mathematics

Finding the shortest move-sequence in the graph-generalized 15-puzzle is NP-hard. (English) Zbl 1343.68093
Goldreich, Oded (ed.), Studies in complexity and cryptography. Miscellanea on the interplay between randomness and computation. In collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kaufman, Leonid Levin, Noam Nisan, Dana Ron, Madhu Sudan, Luca Trevisan, Salil Vadhan, Avi Wigderson, David Zuckerman. Berlin: Springer (ISBN 978-3-642-22669-4/pbk). Lecture Notes in Computer Science 6650, 1-5 (2011).
Summary: Following R. M. Wilson [J. Comb. Theory, Ser. B 16, No. 1, 86–96 (1974; Zbl 0285.05110)], D. S. Johnson [J. Algorithms 4, 397–411 (1983; Zbl 0532.68050)], and D. Kornhauser, G. Miller and P. Spirakis [“Coordinating pebble motion on graphs, the diameter of permutation groups, and applications”, in: Proceedings of the 25th annual symposium on foundations of computer science, FOCS 2011. Los Alamitos, CA: IEEE Computer Society. 241–250 (1984, doi:10.1109/SFCS.1984.715921)], we consider a game that consists of moving distinct pebbles along the edges of an undirected graph. At most one pebble may reside in each vertex at any time, and it is only allowed to move one pebble at a time (which means that the pebble must be moved to a previously empty vertex). We show that the problem of finding the shortest sequence of moves between two given “pebble configuations” is NP-hard.
For the entire collection see [Zbl 1220.68005].

68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C57 Games on graphs (graph-theoretic aspects)
20B40 Computational methods (permutation groups) (MSC2010)
Full Text: DOI
[1] Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness, p. 221. Freeman, San Francisco (1979) · Zbl 0411.68039
[2] Johnson, D.S.: The NP-Completeness Column: An Ongoing Guide. J. of Algorithms 4, 397–411 (1983) · Zbl 0532.68050
[3] Kornhauser, D.M., Miller, G., Spirakis, P.: Coordinating Pebble Motion on Graphs, the Diameter of Permutation Groups, and Applications. In: Proc. of the 25th FOCS, pp. 241–250 (1984)
[4] Wilson, R.W.: Graphs, Puzzles, Homotopy, and Alternating Groups. J. of Comb. Th. (B) 16, 86–96 (1974) · Zbl 0285.05110
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.