Charles Darwin University

CDU eSpace
Institutional Repository

 
CDU Staff and Student only
 

Tractability and hardness of flood-filling games on trees

Fellows, Michael R., Souza, Uéverton dos Santos, Protti, Fabio and da Silva, Maise Dantas (2015). Tractability and hardness of flood-filling games on trees. Theoretical Computer Science,576(April):102-116.

Document type: Journal Article
Citation counts:
Google Scholar Search Google Scholar

IRMA ID 84373604xPUB70
Title Tractability and hardness of flood-filling games on trees
Author Fellows, Michael R.
Souza, Uéverton dos Santos
Protti, Fabio
da Silva, Maise Dantas
Journal Name Theoretical Computer Science
Publication Date 2015
Volume Number 576
Issue Number April
ISSN 0304-3975   (check CDU catalogue open catalogue search in new window)
Scopus ID 2-s2.0-84930250497
Start Page 102
End Page 116
Total Pages 15
Place of Publication Netherlands
Publisher Elsevier BV
HERDC Category C1 - Journal Article (DIISR)
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.
Keywords Flood-It
Free-Flood-It
Shortest common supersequence
NP-hardness
W[1]-hardness
Fixed-parameter tractability
DOI http://dx.doi.org/10.1016/j.tcs.2015.02.008   (check subscription with CDU E-Gateway service for CDU Staff and Students  check subscription with CDU E-Gateway in new window)
 
Versions
Version Filter Type
Access Statistics: 95 Abstract Views  -  Detailed Statistics
Created: Tue, 26 Jul 2016, 12:59:26 CST