(2022) The Largest Connected Subgraph Game.

Text
The_Largest_Connected_Subgraph_Game.pdf Download (1MB)  Preview 
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, if Alice plays optimally, then 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 PSPACEcomplete, even in bipartite graphs of small diameter, and that recognising reflection graphs is GIhard. 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.
Item Type:  Article 

Divisions:  Dániel Marx (DM) 
Depositing User:  Fionn Mc Inerney 
Date Deposited:  23 Sep 2022 08:09 
Last Modified:  23 Sep 2022 08:09 
Primary Research Area:  NRA2: Reliable Security Guarantees 
URI:  https://publications.cispa.saarland/id/eprint/3781 
Actions
Actions (login required)
View Item 