DROPS

Document

DOI: 10.4230/LIPIcs.FUN.2026.26

Hexasort - the Complexity of Stacking Colors on Graphs

Authors: Linus Klocker and Simon Dominik Fink

Published in: LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026)

Abstract

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.

Cite as

Linus Klocker and Simon Dominik Fink. Hexasort - the Complexity of Stacking Colors on Graphs. In 13th International Conference on Fun with Algorithms (FUN 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 366, pp. 26:1-26:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{klocker_et_al:LIPIcs.FUN.2026.26,
  author =	{Klocker, Linus and Fink, Simon Dominik},
  title =	{{Hexasort - the Complexity of Stacking Colors on Graphs}},
  booktitle =	{13th International Conference on Fun with Algorithms (FUN 2026)},
  pages =	{26:1--26:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-417-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{366},
  editor =	{Iacono, John},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.26},
  URN =		{urn:nbn:de:0030-drops-257457},
  doi =		{10.4230/LIPIcs.FUN.2026.26},
  annote =	{Keywords: Hexasort, offline color stacking on graphs, NP-complete, polynomial-time solvable, dynamic programming}
}

Search Results

Documents authored by Klocker, Linus

Hexasort - the Complexity of Stacking Colors on Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message