2026-09-30T09:24:16Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25745 2026-09-23T23:49:12Z ddc:004 open_access

Hexasort - the Complexity of Stacking Colors on Graphs Klocker, Linus Fink, Simon Dominik Hexasort offline color stacking on graphs NP-complete polynomial-time solvable dynamic programming Many popular puzzle and matching games have been analyzed through the lens of computational complexity. Prominent examples include Sudoku [Takayuki Yato and Takahiro Seta, 2003], Candy Crush [Luciano Gualà et al., 2014], and Flood-It [Fellows et al., 2018]. 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Linus Klocker and Simon Dominik Fink 2026 Is Part Of LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FUN.2026.26 urn:nbn:de:0030-drops-257457 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.26 eng https://creativecommons.org/licenses/by/4.0/legalcode