pith. sign in

arxiv: 2606.23837 · v1 · pith:MJE53F3Ynew · submitted 2026-06-22 · 💻 cs.DM · cs.DS

Flood-It with Jewelry -- Characterizing the Game Complexity for Cograph Generalizations

Martin Darm\"untzel , Christian Rosenke , Mark Scheibner This is my paper

Pith reviewed 2026-06-26 05:28 UTC · model grok-4.3

classification 💻 cs.DM cs.DS
keywords Flood-Itgame complexitycographsinduced subgraphsjewelsthin-spider graphsNP-completenesspolynomial-time algorithms
0
0 comments X

The pith

Free Flood-It admits a polynomial-time algorithm on graphs free of the bull, gem, and P5 jewels while both variants are NP-complete on thin-spider graphs, settling the status for 896 of 1024 cograph generalizations.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper classifies the complexity of deciding whether a precolored graph can be made monochromatic in at most k flooding moves, for both the fixed-pivot and free-pivot versions of the game. It starts from the known polynomial-time solvability on cographs and extends the analysis to all 1024 classes obtained by forbidding arbitrary subsets of ten one-vertex extensions of P4, called jewels. A new algorithm shows the free variant is tractable on the 128 classes that forbid at least the bull, gem, and P5; separate reductions show both variants remain hard on thin-spider graphs, which forbid eight jewels and thereby cover 256 additional classes. Together with earlier results the work pins down the complexity for nearly all 1024 families.

Core claim

Our main contribution is a polynomial-time algorithm for Free Flood-It on graphs that are free of the three jewels bull, gem, and P5, 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, P5, and C5, 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.

What carries the argument

The ten jewels (one-vertex extensions of P4) used to define the 1024 forbidden-subgraph classes, together with thin-spider graphs as the explicit NP-complete subclass.

If this is right

  • Free Flood-It belongs to P for every class that forbids the bull, gem, and P5.
  • Both variants are NP-complete for every class whose forbidden set is contained in the eight jewels avoided by thin-spiders.
  • The complexity status is now known for 896 of the 1024 jewel-defined classes extending cographs.
  • Cographs remain the largest known P4-free base on which the free variant is tractable; further jewel combinations inherit this tractability.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same jewel partition may separate tractable and hard cases for other recoloring or token-moving games on graphs.
  • Thin-spider graphs could serve as a canonical hard core for proving hardness of related problems on larger hereditary classes.
  • The 128 undetermined classes may fall into a small number of additional tractable or hard families that can be settled by modest extensions of the current techniques.

Load-bearing premise

The reductions establishing NP-completeness apply directly to thin-spider graphs once those graphs are confirmed to avoid the eight listed jewels.

What would settle it

A polynomial-time algorithm for either variant on thin-spider graphs, or an explicit hard instance of Free Flood-It inside one of the 128 three-jewel-free classes.

Figures

Figures reproduced from arXiv: 2606.23837 by Christian Rosenke, Mark Scheibner, Martin Darm\"untzel.

Figure 1
Figure 1. Figure 1: The jewels, one-vertex extensions of the [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Additional graphs appearing in this paper [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
read the original abstract

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_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$ -- 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_5$, 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_5$, and $C_5$, 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The paper characterizes the complexity of Flood-It and Free Flood-It on the 1024 graph classes obtained by forbidding arbitrary subsets of ten jewels (one-vertex extensions of P4). It gives a polynomial-time algorithm for Free Flood-It on (bull, gem, P5)-free graphs (128 classes) and proves NP-completeness of both variants on thin-spider graphs, which exclude eight jewels (banner, co-banner, chair, gem, house, kite, P5, C5), thereby establishing hardness for 256 classes. Combined with prior results, the complexity is settled for 896 classes.

Significance. If the stated results hold, the work substantially maps the complexity landscape for these games across cograph generalizations, providing both a new tractable class for the free variant and a new hard class that covers many additional forbidden-subgraph combinations.

major comments (1)
  1. [Abstract] Abstract, thin-spider paragraph: the claim that both variants are NP-complete on thin-spider graphs (and thus hardness holds for the 256 classes) is load-bearing. The reductions must be shown to produce thin-spider instances that exclude banner, co-banner, chair, gem, house, kite, P5, and C5; otherwise the mapping from the constructed graphs to the 256 classes fails.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading of the manuscript and for identifying this important point regarding the hardness reduction. We address the comment below.

read point-by-point responses

  1. Referee: [Abstract] Abstract, thin-spider paragraph: the claim that both variants are NP-complete on thin-spider graphs (and thus hardness holds for the 256 classes) is load-bearing. The reductions must be shown to produce thin-spider instances that exclude banner, co-banner, chair, gem, house, kite, P5, and C5; otherwise the mapping from the constructed graphs to the 256 classes fails.

    Authors: We agree that an explicit verification is required to support the mapping to the 256 classes. In the revised version we will add a dedicated lemma immediately following the reduction (new Lemma 5.3) that proves every graph produced by the construction is a thin-spider graph. The argument proceeds by showing that the base instances are thin-spiders and that each gadget is free of the eight listed jewels as induced subgraphs; the proof relies on a short case analysis of possible induced jewels that could arise at gadget boundaries. This addition will make the claim fully rigorous without altering any other part of the hardness proof. revision: yes

Circularity Check

0 steps flagged

No significant circularity; new results are independent of inputs

full rationale

The paper presents an original polynomial-time algorithm for Free Flood-It on bull-gem-P5-free graphs and original NP-completeness proofs on thin-spider graphs as its main contributions. These are combined with external 'known algorithms and hardness results' for the remaining coverage of 896 classes. No self-definitional equations, fitted parameters renamed as predictions, or load-bearing self-citations appear in the abstract or described claims. Structural assertions (e.g., thin-spider graphs excluding listed jewels) are direct graph-theoretic statements, not reductions to the paper's own fitted values or prior self-work. The derivation chain is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Only abstract available; no explicit free parameters, invented entities, or non-standard axioms are mentioned. Relies on standard definitions of induced subgraphs, cographs, and NP-completeness.

axioms (1)
  • standard math Standard definitions of induced subgraphs, P4-free graphs (cographs), and the ten jewels as one-vertex extensions of P4.
    Used to define the 1024 graph classes.

pith-pipeline@v0.9.1-grok · 5892 in / 1324 out tokens · 23095 ms · 2026-06-26T05:28:50.054428+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

14 extracted references · 1 linked inside Pith

  1. [1]

    Brandstädt, F

    A. Brandstädt, F. F. Dragan, H.-O. Le, and R. Mosca. New graph classes of bounded clique-width.Theor. Comp. Sys., 38(5):623–645, Sept. 2005

    2005

  2. [2]

    Clifford, M

    R. Clifford, M. Jalsenius, A. Montanaro, and B. Sach. The complexity of flood filling games. Theory of Computing Systems, 50(1):72–92, Jan 2012

    2012

  3. [3]

    Darmüntzel

    M. Darmüntzel. Die Komplexität des Flood-It-Spiels für Verallgemeinerungen von Co- Graphen. Master’s thesis, University of Rostock, 2025

    2025

  4. [4]

    dos Santos Souza, F

    U. dos Santos Souza, F. Protti, and M. Silva. An algorithmic analysis of flood-it and free-flood-it on graph powers.Discrete Mathematics & Theoretical Computer Science, Vol. 16 no. 3, Dec 2014. 20

    2014

  5. [5]

    M. R. Fellows, U. dos Santos Souza, F. Protti, and M. Dantas da Silva. Tractability and hardness of flood-filling games on trees.Theoretical Computer Science, 576:102–116, 2015

    2015

  6. [6]

    M. R. Fellows, F. A. Rosamond, M. Dantas da Silva, and U. S. Souza.A Survey on the Complexity of Flood-Filling Games, pages 357–376. Springer International Publishing, Cham, 2018

    2018

  7. [7]

    Fleischer and G

    R. Fleischer and G. J. Woeginger. An algorithmic analysis of the honey-bee game. InFun with Algorithms, pages 178–189, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg

    2010

  8. [8]

    Foldes and P

    S. Foldes and P. L. Hammer. Split graphs. InProceedings of the Eighth Southeastern Conference on Combinatorics, Graph Theory and Computing, pages 311–315, Winnipeg, MB, 1977. Utilitas Mathematica Publishing, Inc

    1977

  9. [9]

    Fukui, Y

    H. Fukui, Y. Otachi, R. Uehara, T. Uno, and Y. Uno. On complexity of flooding games on graphs with interval representations. In J. Akiyama, M. Kano, and T. Sakai, editors, Computational Geometry and Graphs, pages 73–84, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg

    2013

  10. [10]

    W. Hon, T. Kloks, F. Liu, H. Liu, and H. Wang. Flood-it on AT-free graphs.CoRR, abs/1511.01806, 2015

    Pith/arXiv arXiv 2015

  11. [11]

    Meeks and A

    K. Meeks and A. Scott. The complexity of flood-filling games on graphs.Discrete Applied Mathematics, 160(7):959–969, 2012

    2012

  12. [12]

    Meeks and A

    K. Meeks and A. Scott. Spanning trees and the complexity of flood-filling games.Theory of Computing Systems, 54:731–753, 2014

    2014

  13. [13]

    Nastos and Y

    J. Nastos and Y. Gao. Bounded search tree algorithms for parameterized cograph dele- tion: Efficient branching rules by exploiting structures of special graph classes.Discrete Mathematics, Algorithms and Applications, 4, 06 2010

    2010

  14. [14]

    Rosenke and M

    C. Rosenke and M. Scheibner. Fanciful figurines flip free flood-it – polynomial-time miniature painting on co-gem-free graphs, 2026. 21

    2026