CISPA
Browse
cispa_all_3781.pdf (1.01 MB)

The Largest Connected Subgraph Game

Download (1.01 MB)
journal contribution
posted on 2023-11-29, 18:06 authored by Julien Bensmail, Foivos Fioravantes, Fionn McInerney, Nicolas Nisse
This paper introduces the largest connected subgraph game played on an undirected graph G. In each round, Alice first colours an uncoloured vertex of G red, and then, Bob colours an uncoloured vertex of G blue, with all vertices initially uncoloured. Once all the vertices are coloured, Alice (Bob, resp.) wins if there is a red (blue, resp.) connected subgraph whose order is greater than the order of any blue (red, resp.) connected subgraph. We first prove that, if Alice plays optimally, then Bob can never win, and define a large class of graphs (called reflection graphs) in which the game is a draw. We then show that determining the outcome of the game is PSPACE-complete, even in bipartite graphs of small diameter, and that recognising reflection graphs is GI-hard. We also prove that the game is a draw in paths if and only if the path is of even order or has at least 11 vertices, and that Alice wins in cycles if and only if the cycle is of odd length. Lastly, we give an algorithm to determine the outcome of the game in cographs in linear time.

History

Preferred Citation

Julien Bensmail, Foivos Fioravantes, Fionn McInerney and Nicolas Nisse. The Largest Connected Subgraph Game. In: Algorithmica. 2022.

Primary Research Area

  • Algorithmic Foundations and Cryptography

Legacy Posted Date

2022-09-23

Journal

Algorithmica

Pages

2533 - 2555

Open Access Type

  • Green

Sub Type

  • Article

BibTeX

@article{cispa_all_3781, title = "The Largest Connected Subgraph Game", author = "Bensmail, Julien and Fioravantes, Foivos and McInerney, Fionn and Nisse, Nicolas", journal="{Algorithmica}", year="2022", }

Usage metrics

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC