On complexity of flooding games on graphs with interval representations

DOI10.1007/978-3-642-45281-9_7MaRDI QIDQ2864330zbMATH OpenOpenAlexFDO

Authors Hiroyuki Fukui, Yota Otachi, Ryuhei Uehara, Takeaki Uno, Yushi Uno

Publication date 6 December 2013

Published in Computational Geometry and Graphs (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1206.6201

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Graph representations (geometric and intersection representations, etc.) (05C62) Analysis of algorithms and problem complexity (68Q25)

Abstract: The flooding games, which are called Flood-It, Mad Virus, or HoneyBee, are a kind of coloring games and they have been becoming popular online. In these games, each player colors one specified cell in his/her turn, and all connected neighbor cells of the same color are also colored by the color. This flooding or coloring spreads on the same color cells. It is natural to consider these new coloring games on more general boards, or general graphs. Recently, computational complexities of the variants of the flooding games on several graph classes have been studied. In this paper, we investigate the flooding games on some graph classes characterized by interval representations. Our results state that the number of colors is a key parameter to determine the computational complexity of the flooding games. When the number of colors is a fixed constant, these games can be solved in polynomial time on an interval graph. On the other hand, if the number of colors is not bounded, the flooding game is NP-complete on a proper interval graph. We also state similar results for split graphs.

Recommendations

• Flooding games on graphs
• A Survey on the Complexity of Flood-Filling Games
• Extremal properties of flood-filling games
• The complexity of flood-filling games on graphs
• The complexity of flood filling games

Cited in

(8)

• On computational complexity of membership test in flow games and linear production games
• Efficient approaches for the flooding problem on graphs
• Twenty years of progress of \(\mathrm{JCDCG}^3\)
• Flooding games on graphs
• How bad is the freedom to Flood-It?
• How Bad is the Freedom to Flood-It?
• Spanning trees and the complexity of flood-filling games
• A Survey on the Complexity of Flood-Filling Games

This page was built for publication: On complexity of flooding games on graphs with interval representations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2864330)