DROPS

Document

DOI: 10.4230/LIPIcs.FUN.2024.11

Hamiltonian Paths and Cycles in NP-Complete Puzzles

Authors: Marnix Deurloo, Mitchell Donkers, Mieke Maarse, Benjamin G. Rin, and Karen Schutte

Published in: LIPIcs, Volume 291, 12th International Conference on Fun with Algorithms (FUN 2024)

Abstract

We show that several pen-and-paper puzzles are NP-complete by giving polynomial-time reductions from the Hamiltonian path and Hamiltonian cycle problems on grid graphs with maximum degree 3. The puzzles include Dotchi Loop, Chains, Linesweeper, Arukone{}₃ (also called Numberlink₃), and Araf. In addition, we show that this type of proof can still be used to prove the NP-completeness of Dotchi Loop even when the available puzzle instances are heavily restricted. Together, these results suggest that this approach holds promise in general for finding NP-completeness proofs of many pen-and-paper puzzles.

Cite as

Marnix Deurloo, Mitchell Donkers, Mieke Maarse, Benjamin G. Rin, and Karen Schutte. Hamiltonian Paths and Cycles in NP-Complete Puzzles. In 12th International Conference on Fun with Algorithms (FUN 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 291, pp. 11:1-11:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{deurloo_et_al:LIPIcs.FUN.2024.11,
  author =	{Deurloo, Marnix and Donkers, Mitchell and Maarse, Mieke and Rin, Benjamin G. and Schutte, Karen},
  title =	{{Hamiltonian Paths and Cycles in NP-Complete Puzzles}},
  booktitle =	{12th International Conference on Fun with Algorithms (FUN 2024)},
  pages =	{11:1--11:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-314-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{291},
  editor =	{Broder, Andrei Z. and Tamir, Tami},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2024.11},
  URN =		{urn:nbn:de:0030-drops-199199},
  doi =		{10.4230/LIPIcs.FUN.2024.11},
  annote =	{Keywords: Hamiltonicity, NP-completeness, complexity theory, pen-and-paper puzzles}
}

Search Results

Documents authored by Donkers, Mitchell

Hamiltonian Paths and Cycles in NP-Complete Puzzles

Abstract

Cite as

Thanks for your feedback!

Could not send message