How Bad is the Freedom to Flood-It?

DOI10.7155/JGAA.00486MaRDI QIDQ4622773zbMATH OpenOpenAlexWikidataFDO

Authors Rémy Belmonte, Mehdi Khosravian Ghadikolaei, Masashi Kiyomi, Michael Lampis, Yota Otachi

Publication date 14 February 2019

Published in Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

Fixed-Flood-ItFree-Flood-It

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Graph algorithms (graph-theoretic aspects) (05C85) Games involving graphs (91A43) Combinatorial games (91A46)

Abstract: Fixed-Flood-It and Free-Flood-It are combinatorial problems on graphs that generalize a very popular puzzle called Flood-It. Both problems consist of recoloring moves whose goal is to produce a monochromatic ("flooded") graph as quickly as possible. Their difference is that in Free-Flood-It the player has the additional freedom of choosing the vertex to play in each move. In this paper, we investigate how this freedom affects the complexity of the problem. It turns out that the freedom is bad in some sense. We show that some cases trivially solvable for Fixed-Flood-It become intractable for Free-Flood-It. We also show that some tractable cases for Fixed-Flood-It are still tractable for Free-Flood-It but need considerably more involved arguments. We finally present some combinatorial properties connecting or separating the two problems. In particular, we show that the length of an optimal solution for Fixed-Flood-It is always at most twice that of Free-Flood-It, and this is tight.

Recommendations

• How bad is the freedom to Flood-It?
• On the termination of flooding
• When does restricting your opponent's freedom hurt you?
• The flood probability distribution tail: How heavy is it?

Cites work

• A Survey on the Complexity of Flood-Filling Games
• Algorithmic meta-theorems for restrictions of treewidth
• Algorithms, kernels and lower bounds for the flood-it game parameterized by the vertex cover number
• An algorithmic analysis of the Honey-Bee game
• Approximating rank-width and clique-width quickly
• Extremal properties of flood-filling games
• Flooding games on graphs
• scientific article; zbMATH DE number 6399334 (Why is no real title available?)
• Kernelization lower bounds through colors and IDs
• Linear time solvable optimization problems on graphs of bounded clique-width
• Modular decomposition and transitive orientation
• On complexity of flooding games on graphs with interval representations
• On problems without polynomial kernels
• On the Grundy number of Cameron graphs
• Parameterized algorithms
• Parameterized Algorithms for Modular-Width
• Parametrized complexity theory.
• Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
• Spanning trees and the complexity of flood-filling games
• The complexity of flood filling games
• The complexity of flood-filling games on graphs
• The complexity of free-flood-it on \(2\times n\) boards
• Tractability and hardness of flood-filling games on trees

Cited in

(2)

• How bad is the freedom to Flood-It?
• The complexity of flood filling games

This page was built for publication: How Bad is the Freedom to Flood-It?

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