Spanning trees and the complexity of flood-filling games

DOI10.1007/S00224-013-9482-ZzbMATH Open1303.05127arXiv1203.2538OpenAlexW2568998114MaRDI QIDQ489766FDOQ489766

Authors: Kitty Meeks, Alex Scott 

Publication date: 21 January 2015

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Flooding games on graphs
• The complexity of free-flood-it on \(2\times n\) boards
• The complexity of flood-filling games on graphs
• The complexity of flood filling games
• An algorithmic analysis of the Honey-Bee game
• On complexity of flooding games on graphs with interval representations

Cited In (11)

• 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
• Extremal properties of flood-filling games
• Complexity and computation of connected zero forcing
• Parameterized complexity of flood-filling games on trees
• Tractability and hardness of flood-filling games on trees
• Flooding games on graphs

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)