Spanning trees and the complexity of flood-filling games

DOI10.1007/S00224-013-9482-ZMaRDI QIDQ489766zbMATH OpenOpenAlexFDO

Authors Kitty Meeks, Alex Scott

Publication date 21 January 2015

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1203.2538, http://eprints.gla.ac.uk/97127/1/97127.pdf

zbMATH Keywords

computational complexitygames on graphsgraph colouring

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43)

Abstract: We consider problems related to the combinatorial game (Free-)Flood-It, in which players aim to make a coloured graph monochromatic with the minimum possible number of flooding operations. We show that the minimum number of moves required to flood any given graph G is equal to the minimum, taken over all spanning trees T of G, of the number of moves required to flood T. This result is then applied to give two polynomial-time algorithms for flood-filling problems. Firstly, we can compute in polynomial time the minimum number of moves required to flood a graph with only a polynomial number of connected subgraphs. Secondly, given any coloured connected graph and a subset of the vertices of bounded size, the number of moves required to connect this subset can be computed in polynomial time.

Recommendations

• The complexity of flood-filling games on graphs
• Tractability and hardness of flood-filling games on trees
• Extremal properties of flood-filling games
• The complexity of flood filling games
• Parameterized complexity of flood-filling games on trees

Cites work

• scientific article; zbMATH DE number 5542185 (Why is no real title available?)
• An algorithmic analysis of the Honey-Bee game
• Flooding games on graphs
• On complexity of flooding games on graphs with interval representations
• 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

Cited in

(11)

• Flooding games on graphs
• How bad is the freedom to Flood-It?
• A Survey on the Complexity of Flood-Filling Games
• How Bad is the Freedom to Flood-It?
• Algorithms, kernels and lower bounds for the flood-it game parameterized by the vertex cover number
• The Flood-It game parameterized by the vertex cover number
• The complexity of flood-filling games on graphs
• Complexity and computation of connected zero forcing
• Extremal properties of flood-filling games
• Parameterized complexity of flood-filling games on trees
• Tractability and hardness of flood-filling games on trees

This page was built for publication: Spanning trees and the complexity of flood-filling games

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