Tractability and hardness of flood-filling games on trees

Michael Fellows, Ueverton Dos Santos Souza, Fabio Protti, Maise Dantas da Silva

    Research output: Contribution to journalArticle

    11 Downloads (Pure)

    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 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.
    Original languageEnglish
    Pages (from-to)102-116
    Number of pages15
    JournalTheoretical Computer Science
    Volume576
    DOIs
    Publication statusPublished - 20 Apr 2015

    Fingerprint Dive into the research topics of 'Tractability and hardness of flood-filling games on trees'. Together they form a unique fingerprint.

  • Cite this

    Fellows, M., Dos Santos Souza, U., Protti, F., & Dantas da Silva, M. (2015). Tractability and hardness of flood-filling games on trees. Theoretical Computer Science, 576, 102-116. https://doi.org/10.1016/j.tcs.2015.02.008