Search

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. [ABSTRACT FROM AUTHOR]

Abstract: An and/or graph is an acyclic, edge-weighted directed graph containing a single source vertex such that every vertex v has a label . A solution subgraph H of an and/or-graph must contain the source and obey the following rule: if an and-vertex (resp. or-vertex) is included in H then all (resp. one) of its out-edges must also be included in H. X-y graphs are defined as a generalization of and/or graphs: every vertex of an x-y graph has a label - , in such a way that if a vertex is included in a solution subgraph H of an x-y graph then of its out-edges must also be included in H. In this work, we analyze complexity aspects (both from the classical and the parameterized point of view) of finding solution subgraphs of minimum weight for and/or and x-y graphs. [Copyright &y& Elsevier]