Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Conference papers

Une version Maker-Breaker du jeu du plus grand sous-graphe connexe

Julien Bensmail 1 Foivos Fioravantes 1 Fionn Mc Inerney 2 Nicolas Nisse 1 Nacim Oijid 3 
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
3 GOAL - Graphes, AlgOrithmes et AppLications
LIRIS - Laboratoire d'InfoRmatique en Image et Systèmes d'information
Résumé : Dans le jeu du plus grand sous-graphe connexe, deux joueurs, Anaïs et Gilles, s'affrontent en colorant les sommets d'un graphe. À chaque tour, Anaïs colore un sommet non coloré en rouge puis Gilles colore un sommet non coloré en bleu. Lorsque tous les sommets sont colorés, le joueur dont la couleur induit la plus grande composante connexe gagne. Ce jeu a été défini dans [Bensmail et al, WG'21 et AlgoTel'21] où il a été montré entre autres que Gilles n'a jamais de stratégie gagnante (au mieux, il peut espérer une égalité). Nous étudions la version de ce jeu où on se donne aussi un entier $k\geq 1$. Dans ce cas, Anaïs gagne si elle crée une composante connexe rouge de taille au moins et Gilles gagne sinon. Étant donné un graphe $G$, nous étudions $c_g(G)$, le plus grand entier qui garantit la victoire d'Anaïs. Outre le fait que cela donne une chance à Gilles de gagner, cette variante fait partie de la famille des jeux combinatoires Maker-Breaker, qui ont été très étudiés. De plus, cette variante offre des outils différents pour mieux comprendre la version Maker-Maker initiale. En particulier, nous étudions les graphes A-parfaits pour lesquels Anaïs peut gagner en créant une unique composante rouge, i.e., les graphes à n sommets tels que $c_g(G) = \lceil n/2 \rceil$. Nous montrons que le calcul de $c_g(G)$ est PSPACE-complet dans les graphes bipartis, scindés (split) ou planaires, et que et une stratégie correspondante peuvent être calculés en temps linéaire dans les graphes $P_4$-clairsemés (généralisant les cographes). Nous donnons ensuite des conditions suffisantes (liées aux degrés ou au nombre d'arêtes) pour qu'un graphe soit A-parfait. Un résultat surprenant est qu'il n'existe aucun graphe 3-régulier A-parfait avec plus de 132 sommets.
Document type :
Conference papers
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-03648321
Contributor : Foivos Fioravantes Connect in order to contact the contributor
Submitted on : Monday, April 25, 2022 - 9:11:32 AM
Last modification on : Sunday, May 1, 2022 - 3:18:04 AM

File

The_Largest_Connected_Subgraph...
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03648321, version 1

Citation

Julien Bensmail, Foivos Fioravantes, Fionn Mc Inerney, Nicolas Nisse, Nacim Oijid. Une version Maker-Breaker du jeu du plus grand sous-graphe connexe. AlgoTel 2022 - 24èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, May 2022, Saint-Rémy-Lès-Chevreuse, France. ⟨hal-03648321⟩

Share

Metrics

Record views

52

Files downloads

6