The Maker-Breaker Largest Connected Subgraph Game - Archive ouverte HAL Access content directly
Reports (Research Report) Year : 2021

The Maker-Breaker Largest Connected Subgraph Game

(1) , (1) , (2) , (1) , (3)


Given a graph $G$ and an integer $k \in \mathbb{N}$, we introduce the following Maker-Breaker game played in $G$. Each round, first Alice colours an uncoloured vertex of $G$ red, and then Bob colours an uncoloured vertex blue (if any remain). Once all the vertices have been coloured, Alice wins if there exists a connected red component of order at least $k$, and if not, then Bob wins. This game is a Maker-Breaker version of the Largest Connected Subgraph game introduced in [Bensmail, Fioravantes, Mc Inerney, and Nisse, WG 2021]. We are interested in computing $c_g(G)$, which is the maximum $k$ such that Alice wins in $G$, regardless of what Bob does.Given a graph $G$ and an integer $k\geq 1$, we prove that deciding whether $c_g(G)\geq k$ is PSPACE-complete, even if $G$ is restricted to be in the class of bipartite graphs of diameter~$4$, split graphs, or planar graphs. Then, we focus on {\it A-perfect} graphs, namely, graphs for which $c_g(G)=\left \lceil \frac{|V(G)|}{2}\right \rceil$, {\it i.e.}, the maximum possible value. We show that there exist arbitrarily large A-perfect $d$-regular graphs for any $d \geq 4$, but, surprisingly, that no cubic graph with order at least $133$ is A-perfect. Moreover, we give sufficient conditions, in terms of the number of edges or the maximum and minimum degree, for a graph to be A-perfect.Finally, we show that $c_g(G)$ can be computed in polynomial time when $G$ is a $P_4$-sparse graph (a superclass of cographs). We conclude with many open questions. In particular, natural graph classes such as trees and grid-like graphs seem to be difficult to deal with. We only give partial results in the case of some grid-like graphs.
Fichier principal
Vignette du fichier
The_Largest_Connected_Subgraph_Game__maker_breaker_version(6).pdf (560.61 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-03500888 , version 1 (22-12-2021)


  • HAL Id : hal-03500888 , version 1


Julien Bensmail, Foivos Fioravantes, Fionn Mc Inerney, Nicolas Nisse, Nacim Oijid. The Maker-Breaker Largest Connected Subgraph Game. [Research Report] Université Côte d’Azur, CNRS, Inria, I3S, Biot, France. 2021. ⟨hal-03500888⟩
120 View
108 Download


Gmail Facebook Twitter LinkedIn More