2026-08-21T18:02:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27421 2026-08-21T14:42:39Z ddc:004 open_access

Flood-It with Jewelry - Characterizing the Game Complexity for Cograph Generalizations Darmüntzel, Martin Rosenke, Christian Scheibner, Mark Flood-It Free Flood-It cograph generalizations polynomial time algorithms NP-completeness Flood-It is a single-player game played on a precolored graph G, where the objective is to make G monochromatic using as few flooding moves as possible. In each move, a color c is selected and all vertices reachable from a fixed pivot vertex via a monochromatic path are recolored with c. In the free variant, the pivot may be chosen anew in every move. Deciding whether a graph can be made monochromatic in at most k moves is NP-complete for both variants, fixed and free. This hardness persists even under strong structural restrictions such as split graphs and trees. The Free Flood-It variant is generally considered more difficult than its fixed-pivot counterpart, as it remains hard on several graph classes where the latter becomes tractable, including co-comparability and AT-free graphs. Cographs, that is, P₄-free graphs, are among the few classes on which even Free Flood-It is solvable in polynomial time and therefore serve as our starting point. We consider the ten natural one-vertex extensions of P₄ - referred to as jewels - and study the complexity of both flooding games on the 1024 graph classes obtained by forbidding subsets of these graphs as induced subgraphs. Our main contribution is a polynomial-time algorithm for Free Flood-It on graphs that are free of the three jewels bull, gem, and P₅, covering 128 of the 1024 classes. In addition, we prove that both variants remain NP-complete on thin-spider graphs, which exclude the eight jewels banner, co-banner, chair, gem, house, kite, P₅, and C₅, thereby establishing hardness for 256 additional classes. Combined with known algorithms and hardness results, our work determines the complexity of both Flood-It variants for 896 of the 1024 considered graph classes. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Martin Darmüntzel and Christian Rosenke and Mark Scheibner 2026 Is Part Of LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2026.40 urn:nbn:de:0030-drops-274216 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.40 eng https://creativecommons.org/licenses/by/4.0/legalcode