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
| CREATOR | Linus Klocker, Simon Dominik Fink |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 52414 |
| LICENSE | http://creativecommons.org/licenses/by-sa/4.0/ |
| RIGHTS | CC BY SA |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.01244