Abstract | ||
---|---|---|
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 W1]-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. |
Year | DOI | Venue |
---|---|---|
2015 | 10.1016/j.tcs.2015.02.008 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
w1]-hardness,flood-it,free-flood-it,np-hardness,fixed-parameter tractability,shortest common supersequence | Journal | 576 |
Issue | ISSN | Citations |
C | 0304-3975 | 2 |
PageRank | References | Authors |
0.39 | 23 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Michael R. Fellows | 1 | 4138 | 319.37 |
Uéverton dos Santos Souza | 2 | 12 | 2.63 |
Fábio Protti | 3 | 357 | 46.14 |
Maise Dantas da Silva | 4 | 59 | 5.72 |