The Flood-It game parameterized by the vertex cover number

U.D.S. Souza, Frances Rosamond, Michael Fellows, Fabio Protti, Maise Dantas da Silva

    Research output: Contribution to journalArticleResearchpeer-review

    Abstract

    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×n grids. It is known that Flood-It remains NP-hard even for 3×n grids and for instances with bounded number of colors, diameter, or treewidth. In contrast, in this work we show that Flood-It is fixed-parameter tractable when parameterized by the vertex cover number, and admits a polynomial kernelization when, besides the vertex cover number, the number of colors is an additional parameter.
    Original languageEnglish
    Pages (from-to)35-40
    Number of pages6
    JournalElectronic Notes in Discrete Mathematics
    Volume50
    DOIs
    Publication statusPublished - Dec 2015

    Fingerprint

    Vertex Cover
    Game
    Color
    Flooding
    Combinatorial Games
    Grid
    Kernelization
    Colored Graph
    Polynomials
    Alike
    Treewidth
    Pivot
    Combinatorial Problems
    Subgraph
    NP-complete problem
    Generalise
    Polynomial
    Graph in graph theory
    Vertex of a graph

    Cite this

    Souza, U. D. S., Rosamond, F., Fellows, M., Protti, F., & Dantas da Silva, M. (2015). The Flood-It game parameterized by the vertex cover number. Electronic Notes in Discrete Mathematics, 50, 35-40. https://doi.org/10.1016/j.endm.2015.07.007
    Souza, U.D.S. ; Rosamond, Frances ; Fellows, Michael ; Protti, Fabio ; Dantas da Silva, Maise. / The Flood-It game parameterized by the vertex cover number. In: Electronic Notes in Discrete Mathematics. 2015 ; Vol. 50. pp. 35-40.
    @article{4e693568bed84ac8a32ee56b6cd0ef66,
    title = "The Flood-It game parameterized by the vertex cover number",
    abstract = "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×n grids. It is known that Flood-It remains NP-hard even for 3×n grids and for instances with bounded number of colors, diameter, or treewidth. In contrast, in this work we show that Flood-It is fixed-parameter tractable when parameterized by the vertex cover number, and admits a polynomial kernelization when, besides the vertex cover number, the number of colors is an additional parameter.",
    author = "U.D.S. Souza and Frances Rosamond and Michael Fellows and Fabio Protti and {Dantas da Silva}, Maise",
    year = "2015",
    month = "12",
    doi = "10.1016/j.endm.2015.07.007",
    language = "English",
    volume = "50",
    pages = "35--40",
    journal = "Electronic Notes in Discrete Mathematics",
    issn = "1571-0653",
    publisher = "Elsevier",

    }

    Souza, UDS, Rosamond, F, Fellows, M, Protti, F & Dantas da Silva, M 2015, 'The Flood-It game parameterized by the vertex cover number', Electronic Notes in Discrete Mathematics, vol. 50, pp. 35-40. https://doi.org/10.1016/j.endm.2015.07.007

    The Flood-It game parameterized by the vertex cover number. / Souza, U.D.S.; Rosamond, Frances; Fellows, Michael; Protti, Fabio; Dantas da Silva, Maise.

    In: Electronic Notes in Discrete Mathematics, Vol. 50, 12.2015, p. 35-40.

    Research output: Contribution to journalArticleResearchpeer-review

    TY - JOUR

    T1 - The Flood-It game parameterized by the vertex cover number

    AU - Souza, U.D.S.

    AU - Rosamond, Frances

    AU - Fellows, Michael

    AU - Protti, Fabio

    AU - Dantas da Silva, Maise

    PY - 2015/12

    Y1 - 2015/12

    N2 - 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×n grids. It is known that Flood-It remains NP-hard even for 3×n grids and for instances with bounded number of colors, diameter, or treewidth. In contrast, in this work we show that Flood-It is fixed-parameter tractable when parameterized by the vertex cover number, and admits a polynomial kernelization when, besides the vertex cover number, the number of colors is an additional parameter.

    AB - 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×n grids. It is known that Flood-It remains NP-hard even for 3×n grids and for instances with bounded number of colors, diameter, or treewidth. In contrast, in this work we show that Flood-It is fixed-parameter tractable when parameterized by the vertex cover number, and admits a polynomial kernelization when, besides the vertex cover number, the number of colors is an additional parameter.

    U2 - 10.1016/j.endm.2015.07.007

    DO - 10.1016/j.endm.2015.07.007

    M3 - Article

    VL - 50

    SP - 35

    EP - 40

    JO - Electronic Notes in Discrete Mathematics

    JF - Electronic Notes in Discrete Mathematics

    SN - 1571-0653

    ER -