HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

Connexions ! Le jeu du plus grand sous-graphe connexe

Julien Bensmail 1 Foivos Fioravantes 1 Fionn Mc Inerney 2 Nicolas Nisse 1
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : 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 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.
Document type :
Conference papers
Complete list of metadata

Contributor : Foivos Fioravantes Connect in order to contact the contributor
Submitted on : Thursday, May 6, 2021 - 3:23:58 PM
Last modification on : Friday, January 21, 2022 - 3:11:42 AM


Files produced by the author(s)


  • HAL Id : hal-03211446, version 2


Julien Bensmail, Foivos Fioravantes, Fionn Mc Inerney, Nicolas Nisse. Connexions ! Le jeu du plus grand sous-graphe connexe. ALGOTEL 2021 - 23èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, Sep 2021, La Rochelle, France. ⟨hal-03211446v2⟩



Record views


Files downloads