Hexasort – The Complexity of Stacking Colors on Graphs

Linus Klocker, Simon Dominik Fink · 2026

Read Hexasort – The Complexity of Stacking Colors on Graphs by Linus Klocker, Simon Dominik Fink (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-01244.txt.

Description

Klocker and Fink prove the stacking puzzle Hexasort is NP-hard, meaning no fast general solution is expected, even for single-color stacks and tightly constrained graph classes. In Hexasort, colored stacks sit on graph vertices, and adjacent same-color stacks merge and vanish by fixed rules. Their proof reaches strong NP-hardness on trees of bounded height or degree. They also find settings where the problem becomes polynomial-time solvable and give dynamic programming algorithms for those cases.

Catalog record

CREATORLinus Klocker, Simon Dominik Fink
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE52414
LICENSEhttp://creativecommons.org/licenses/by-sa/4.0/
RIGHTSCC BY SA
SOURCEarXiv

Source: https://arxiv.org/abs/2603.01244

Browse the full library · About the Tower of Babel