Klocker, L., & Fink, S. D. (2026). Hexasort – the Complexity of Stacking Colors on Graphs. In J. Iacono (Ed.), 13th International Conference on Fun with Algorithms (FUN 2026). Schloss Dagstuhl. https://doi.org/10.4230/LIPIcs.FUN.2026.26
E192-01 - Forschungsbereich Algorithms and Complexity
-
Published in:
13th International Conference on Fun with Algorithms (FUN 2026)
-
ISBN:
9783959774178
-
Volume:
366
-
Date (published):
15-May-2026
-
Event name:
13th International Conference on Fun with Algorithms (FUN 2026)
en
Event date:
18-May-2026 - 22-May-2026
-
Event place:
Porquerolles, France
-
Number of Pages:
12
-
Publisher:
Schloss Dagstuhl, Leibniz
-
Peer reviewed:
Yes
-
Keywords:
dynamic programming; Hexasort; NP-complete; offline color stacking on graphs; polynomial-time solvable
en
Abstract:
Many popular puzzle and matching games have been analyzed through the lens of computational complexity. Prominent examples include Sudoku [13], Candy Crush [7], and Flood-It [4]. A common theme among these widely played games is that their generalized decision versions are NP-hard, which is often thought of as a source of their inherent difficulty and addictive appeal to human players. In this paper, we study a popular single-player stacking game commonly known as Hexasort. The game can be modelled as placing colored stacks onto the vertices of a graph, where adjacent stacks of the same color merge and vanish according to deterministic rules. We prove that Hexasort is NP-hard, even when restricted to single-color stacks and progressively more constrained classes of graphs, culminating in strong NP-hardness on trees of either bounded height or degree. Towards fixed-parameter tractable algorithms, we identify settings in which the problem becomes polynomial-time solvable and present dynamic programming algorithms.
