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.

Elementary net system feasibility is the problem to decide for a given automaton A if there is a certain boolean Petri net with a state graph isomorphic to A. This is equivalent to the conjunction of the state separation property (SSP) and the event state separation property (ESSP). Since feasibility, SSP and ESSP are known to be NP-complete in general, there was hope that the restriction of graph parameters for A can lead to tractable and practically relevant subclasses. In this paper, we analyze event manifoldness, the amount of occurrences that an event can have in A, and state degree, the number of allowed successors and predecessors of states in A, as natural input restrictions. Recently, it has been shown that all three decision problems, feasibility, SSP and ESSP, remain NP-complete for linear A where every event occurs at most three times. Here, we show that these problems remain hard even if every event occurs at most twice. Nevertheless, this has to be paid by relaxing the restriction on state degree, allowing every state to have two successor and two predecessor states. As we also show that SSP becomes tractable for linear A where every event occurs at most twice the only open cases left are ESSP and feasibilty for the same input restriction.