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

The Largest Connected Subgraph Game

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 : We introduce the largest connected subgraph game played on an undirected graph $G$. In each round, Alice colours an uncoloured vertex of $G$ red, and then, Bob colours an uncoloured vertex blue, with no vertices initially coloured. Once all the vertices are coloured, Alice (Bob, resp.) wins if there is a red (blue, resp.) connected subgraph of order greater than the order of any blue (red, resp.) connected subgraph. If neither player wins, it is a draw. We first prove that Bob can never win, and define a large class of graphs ( reflection graphs) in which the game is a draw. We show that determining the outcome of the game is PSPACE-complete in bipartite graphs of small diameter, 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 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.
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:27:45 PM
Last modification on : Friday, January 21, 2022 - 3:12:53 AM
Long-term archiving on: : Saturday, August 7, 2021 - 7:16:43 PM


Files produced by the author(s)



Julien Bensmail, Foivos Fioravantes, Fionn Mc Inerney, Nicolas Nisse. The Largest Connected Subgraph Game. WG 2021 - The 47th International Workshop on Graph-Theoretic Concepts in Computer Science, Jun 2021, Warsaw, Poland. pp.296-307, ⟨10.1007/978-3-030-86838-3_23⟩. ⟨hal-03219636⟩



Record views


Files downloads