CISPA
Browse
cispa_all_3549.pdf (1.01 MB)

The Largest Connected Subgraph Game

Download (1.01 MB)
conference contribution
posted on 2023-11-29, 18:18 authored by Julien Bensmail, Foivos Fioravantes, Fionn Mc Inerney, Nicolas Nisse
We introduce the largest connected subgraph game played on an undirected graph G. Each round, Alice colours an uncoloured vertex of G red, and then, Bob colours one blue. Once every vertex is coloured, Alice (Bob, resp.) wins if there is a red (blue, resp.) connected subgraph whose order is greater than that of any blue (red, resp.) connected subgraph. If neither player wins, it is a draw. We prove that Alice can ensure Bob never wins, and define a class of graphs (reflection graphs) in which the game is a draw. We show that the game is PSPACE-complete in bipartite graphs of diameter 5, and that recognising reflection graphs is GI-hard. We prove that the game is a draw in paths if and only if the path has even order or at least 11 vertices, and that Alice wins in cycles if and only if the cycle is of odd order. We also give an algorithm computing the outcome of the game in cographs in linear time.

History

Preferred Citation

Julien Bensmail, Foivos Fioravantes, Fionn Inerney and Nicolas Nisse. The Largest Connected Subgraph Game. In: International Workshop on Graph-Theoretic Concepts in Computer Science (WG). 2021.

Primary Research Area

  • Reliable Security Guarantees

Name of Conference

International Workshop on Graph-Theoretic Concepts in Computer Science (WG)

Legacy Posted Date

2021-12-14

Open Access Type

  • Green

BibTeX

@inproceedings{cispa_all_3549, title = "The Largest Connected Subgraph Game", author = "Bensmail, Julien and Fioravantes, Foivos and Inerney, Fionn Mc and Nisse, Nicolas", booktitle="{International Workshop on Graph-Theoretic Concepts in Computer Science (WG)}", year="2021", }

Usage metrics

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC