Algorithms, kernels and lower bounds for the Flood-It game parameterized by the vertex cover number

摘要

Flood-It is a combinatorial problem on a colored graph whose aim is to make the graph monochromatic using the minimum number of flooding moves, relatively to a pivot vertex p. A Flooding move consists of changing the color of the monochromatic component (maximal monochromatic connected subgraph) containing p. This problem generalizes a combinatorial game named alike which is played on m x n grids. It is known that Flood It is NP-hard even for 3 x n grids and for instances with bounded number of colors, diameter, treewidth, or pathwidth. In [Fellows, Souza, Protti, Dantas da Silva, Tractability and hardness of Flood-filling games on trees, Theoretical Computer Science, 576, 102-116, 2015] it is shown that Flood-It is W[1]-hard when played on trees with bounded number of colors, and the number of leaves is a single parameter. Contrasting with such results, in this work we show that Flood-It is fixed-parameter tractable when parameterized by either the vertex cover number or the neighborhood diversity. Additionally, we prove that Flood-It does not admit a polynomial kernel when the vertex cover number is a single parameter, unless coNP subset of NP / poly. Finally, lower bounds based on the (Strong) Exponential Time Hypothesis as well as an upper bound for the required time to solve Flood-lt are also provided. (C) 2017 Elsevier B.V. All rights reserved.