TY - JOUR
T1 - Tractability and hardness of flood-filling games on trees
AU - Fellows, Michael
AU - Dos Santos Souza, Ueverton
AU - Protti, Fabio
AU - Dantas da Silva, Maise
PY - 2015/4/20
Y1 - 2015/4/20
N2 - This work presents new results on flood-filling games, Flood-It and Free-Flood-It, in which the player aims to make the board monochromatic with a minimum number of flooding moves. A flooding move consists of changing the color of the monochromatic component containing a vertex p (the pivot of the move). These games are originally played on grids; however, when played on trees, we have interesting applications and significant effects on problem complexity. In this paper, a complete mapping of the complexity of flood-filling games on trees is made, charting the consequences of single and aggregate parameterizations by: number of colors, number of moves, maximum distance from the pivot, number of occurrences of a color, number of leaves, and difference between number of moves and number of colors.We show that Flood-It on trees and Restricted Shortest Common Supersequence (RSCS) are analogous problems, in the sense that they can be translated from one to another, preserving complexity issues; this implies interesting FPT and W[1]-hard cases to Flood-It. Restricting attention to phylogenetic colored trees (where each color occurs at most once in any root-leaf path, in order to model phylogenetic sequences), we also show some impressive NP-hard and FPT results for both games. In addition, we prove that Flood-It and Free-Flood-It remain NP-hard when played on 3-colored trees, which closes an open question posed by Fleischer and Woeginger. Finally, we present a general framework for reducibility from Flood-It to Free-Flood-It; some NP-hard cases for Free-Flood-It can be derived using this approach. � 2015 Elsevier B.V.
AB - This work presents new results on flood-filling games, Flood-It and Free-Flood-It, in which the player aims to make the board monochromatic with a minimum number of flooding moves. A flooding move consists of changing the color of the monochromatic component containing a vertex p (the pivot of the move). These games are originally played on grids; however, when played on trees, we have interesting applications and significant effects on problem complexity. In this paper, a complete mapping of the complexity of flood-filling games on trees is made, charting the consequences of single and aggregate parameterizations by: number of colors, number of moves, maximum distance from the pivot, number of occurrences of a color, number of leaves, and difference between number of moves and number of colors.We show that Flood-It on trees and Restricted Shortest Common Supersequence (RSCS) are analogous problems, in the sense that they can be translated from one to another, preserving complexity issues; this implies interesting FPT and W[1]-hard cases to Flood-It. Restricting attention to phylogenetic colored trees (where each color occurs at most once in any root-leaf path, in order to model phylogenetic sequences), we also show some impressive NP-hard and FPT results for both games. In addition, we prove that Flood-It and Free-Flood-It remain NP-hard when played on 3-colored trees, which closes an open question posed by Fleischer and Woeginger. Finally, we present a general framework for reducibility from Flood-It to Free-Flood-It; some NP-hard cases for Free-Flood-It can be derived using this approach. � 2015 Elsevier B.V.
KW - Color
KW - Filling
KW - Forestry
KW - Hardness
KW - Complete mappings
KW - Complexity issues
KW - Fixed-parameter tractability
KW - Free-Flood-It
KW - Monochromatic components
KW - NP-hardness
KW - Problem complexity
KW - Shortest common supersequence
KW - Floods
KW - Algorithms
KW - Optimization
U2 - 10.1016/j.tcs.2015.02.008
DO - 10.1016/j.tcs.2015.02.008
M3 - Article
VL - 576
SP - 102
EP - 116
JO - Theoretical Computer Science
JF - Theoretical Computer Science
SN - 0304-3975
ER -