The Maker-Breaker Largest Connected Subgraph Game - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Theoretical Computer Science Année : 2021

The Maker-Breaker Largest Connected Subgraph Game

Résumé

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
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

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

Identifiants

Citer

Julien Bensmail, Foivos Fioravantes, Fionn Mc Inerney, Nicolas Nisse, Nacim Oijid. The Maker-Breaker Largest Connected Subgraph Game. Theoretical Computer Science, 2021, 943, pp.102-120. ⟨10.1016/j.tcs.2022.12.014⟩. ⟨hal-03500888v1⟩
234 Consultations
118 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More