DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2026.40

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

Authors: Martin Darmüntzel, Christian Rosenke, and Mark Scheibner

Published in: LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)

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₄-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.

Cite as

Martin Darmüntzel, Christian Rosenke, and Mark Scheibner. Flood-It with Jewelry - Characterizing the Game Complexity for Cograph Generalizations. In 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 386, pp. 40:1-40:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{darmuntzel_et_al:LIPIcs.MFCS.2026.40,
  author =	{Darm\"{u}ntzel, Martin and Rosenke, Christian and Scheibner, Mark},
  title =	{{Flood-It with Jewelry - Characterizing the Game Complexity for Cograph Generalizations}},
  booktitle =	{51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)},
  pages =	{40:1--40:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-442-0},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{386},
  editor =	{Kouck\'{y}, Michal and Petrișan, Daniela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.40},
  URN =		{urn:nbn:de:0030-drops-274216},
  doi =		{10.4230/LIPIcs.MFCS.2026.40},
  annote =	{Keywords: Flood-It, Free Flood-It, cograph generalizations, polynomial time algorithms, NP-completeness}
}

Document

DOI: 10.4230/LIPIcs.CONCUR.2018.16

Narrowing down the Hardness Barrier of Synthesizing Elementary Net Systems

Authors: Ronny Tredup and Christian Rosenke

Published in: LIPIcs, Volume 118, 29th International Conference on Concurrency Theory (CONCUR 2018)

Abstract

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.

Cite as

Ronny Tredup and Christian Rosenke. Narrowing down the Hardness Barrier of Synthesizing Elementary Net Systems. In 29th International Conference on Concurrency Theory (CONCUR 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 118, pp. 16:1-16:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{tredup_et_al:LIPIcs.CONCUR.2018.16,
  author =	{Tredup, Ronny and Rosenke, Christian},
  title =	{{Narrowing down the Hardness Barrier of Synthesizing Elementary Net Systems}},
  booktitle =	{29th International Conference on Concurrency Theory (CONCUR 2018)},
  pages =	{16:1--16:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-087-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{118},
  editor =	{Schewe, Sven and Zhang, Lijun},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2018.16},
  URN =		{urn:nbn:de:0030-drops-95546},
  doi =		{10.4230/LIPIcs.CONCUR.2018.16},
  annote =	{Keywords: Elementary net systems, Petri net synthesis, NP-completeness, Parameterized Complexity}
}

Search Results

Documents authored by Rosenke, Christian

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

Abstract

Cite as

Narrowing down the Hardness Barrier of Synthesizing Elementary Net Systems

Abstract

Cite as

Thanks for your feedback!

Could not send message