Flood-It with Jewelry – Characterizing the Game Complexity for Cograph Generalizations
Martin Darmüntzel, Christian Rosenke, Mark Scheibner · 2026
Read Flood-It with Jewelry – Characterizing the Game Complexity for Cograph Generalizations by Martin Darmüntzel, Christian Rosenke, Mark Scheibner (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-2606-23837.txt.
Introduction
Darmüntzel, Rosenke, and Scheibner map out how hard a color flooding game is across a large family of restricted graphs, in a 2026 paper on computational complexity. In Flood-It, a player picks colors and recolors everything reachable from a pivot point through same colored paths, aiming to make the graph one color in few moves. Whether a target number of moves suffices is NP complete to decide, even on restricted graphs. Cographs are a rare easy case; the authors extend their pattern in ten steps, calling the extensions jewels.
Forbidding subsets of the jewels defines one thousand twenty four classes. The team gives a polynomial time algorithm for the free pivot variant on graphs avoiding three jewels, settling one hundred twenty eight classes. Both variants stay NP complete on thin spider graphs, settling two hundred fifty six more. Complexity is now determined for eight hundred ninety six classes.
Catalog record
| CREATOR | Martin Darmüntzel, Christian Rosenke, Mark Scheibner |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 80 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.23837
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Flood-It with Jewelry – Characterizing the Game Complexity for Cograph Generalizations Martin Darmüntzel, Christian Rosenke, Mark Scheibner Abstract Flood-It is a single-player game played on a precolored graph G G , where the objective is to make G G monochromatic using as few flooding moves as possible. In each move, a color c c is selected and all vertices reachable from a fixed pivot vertex via a monochromatic path are recolored with c 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 k moves is 𝖭𝖯 \mathsf{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 4 P_{4} -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 4 P_{4} – referred to as jewels – and study the complexity of both flooding games on the 1024 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 5 P_{5} , covering 128 128 of the 1024 1024 classes. In addition, we prove that both variants remain 𝖭𝖯 \mathsf{NP} -complete on thin-spider graphs, which exclude the eight jewels banner , co-banner , chair , gem , house , kite , P 5 P_{5} , and C 5 C_{5} , thereby establishing hardness for 256 256 additional classes. Combined with known algorithms and hardness results, our work determines the complexity of both Flood-It variants for 896 896 of the 1024 1024 considered graph classes. 1 Introduction Flood-It and several of its variants have been studied extensively between 2010 and 2020. This substantial body of work has shown that computing optimal strategies remains computationally hard, even under severe restrictions on the input. For comprehensive overviews of known hardness results and the comparatively few polynomial-time solvable cases, we refer the interested reader to the excellent surveys by Fellows et al. [ 6 ] and Fleischer and Woeginger [ 7 ] . While the original flood-filling game is played on precolored grids, the notion of a playfield has been generalized in the literature to arbitrary graphs to better capture and analyze the underlying algorithmic challenges. In this paper, we focus on single-player variants, where each game is described by a move order , that is, a sequence of moves, each of which floods a chosen color c onto all vertices w that are reachable from a pivot vertex v via a monochromatic path, that is, a path from v to w whose vertices all have the same color at the time of the move. The goal of the game is to make the playfield graph G monochromatic; accordingly, any move order that achieves this is called a strategy for G . In the variant called Free Flood-It the player may freely choose the pivot vertex in every move. Naturally, if the pivot is a fixed vertex specified as part of the input, we obtain the (fixed) Flood-It game. In both variants, the objective is to find a strategy of minimum length. There are corresponding decision variants of these problems that additionally take an integer k as input and ask whether there exists a strategy using at most k moves. Since the relevant variant, optimization or decision, will always be clear from context, this paper does not introduce separate notations. It is known that the computational problems underlying these flood-filling games, Flood-It and Free Flood-It , remain intractable even under severe input restrictions such as split graphs [ 7 , 9 ] . In particular, both problems are \mathsf{NP} -hard when the input playfield is a tree [ 5 ] or a grid [ 2 ] , even if it is initially colored with only three colors. Only very few non-trivial graph classes are known on which Flood-It (FIt, for short) is tractable, including co-comparability [ 7 ] and AT-free graphs [ 9 ] . In contrast, Free Flood-It (FFIt, for short) remains hard even on these classes. For many years, polynomial-time solvability of the free variant has been known only for very restricted grids [ 11 ] , as well as for simple paths and cycles [ 12 ] . However, for the second powers of paths and cycles [ 4 ] , FFIt becomes \mathsf{NP} -hard again. As part of the algorithmic techniques developed in this paper, we show that deciding whether a graph G can be made monochromatic using exactly k-1 free moves – one for each of the k colors used in G except the last – can be done in polynomial time, independent of the presence of certain structures in the graph and the initial coloring. Indeed, if the playfield initially uses k distinct colors, any strategy requires at least k-1 moves, since each move can eliminate at most one color. Given the apparent resistance of FFIt to efficient algorithms, it is somewhat surprising that deciding the existence of a k-1 -move strategy is always in polynomial time. The main contribution of this paper, however, is motivated by the recent result [ 14 ] that FFIt is polynomial-time solvable on cographs – the graphs without induced P_{4} . This naturally raises the question of how the restriction of forbidding induced P_{4} can be relaxed without losing tractability. In [ 14 ] , this question is addressed by considering the extension of P_{4} by an independent vertex and deriving a significantly more involved polynomial-time algorithm for graphs that are free of induced co-gem s; see Figure 1 (f). It is well known that the co-gem is not the only graph generalizing P_{4} , and that there are exactly ten non-isomorphic one-vertex extensions of P_{4} ; see, for example, [ 1 ] . As illustrated in Figure 1 , these graphs can be viewed as interpolating between the co-gem and its complement, the gem , by selecting a subset of the four edges that connect the additional vertex to the underlying P_{4} . Motivated by this interpretation, we refer to these graphs collectively as jewels . (a) gem (b) P_{5} (c) chair (d) banner (e) C_{5} (also co- C_{5} ) (f) co-gem (g) house (co- P_{5} ) (h) kite (co- chair ) (i) co-banner (j) bull (also co- bull ) Figure 1: The jewels, one-vertex extensions of the P_{4} , given with common name and complement graph relation Now, if we consider arbitrary subsets of these small graphs as forbidden induced subgraphs, we obtain a large collection of natural generalizations of cographs. Based on this, we continue the line of inquiry initiated in [ 14 ] in a natural way and ask, for every possible subset \mathcal{G} of the jewels, what the complexity of (Free) Flood-It is