Topological Network-Control Games
Published in International Computing and Combinatorics Conference, 2023
The paper introduces new combinatorial games, called topological network-control games, played on graphs. These games model the influence of competing two parties aiming to control a given network. In a such game given the network, the players move alternatively. At each turn, a player selects an unclaimed vertex and its unclaimed neighbours within distance $t$. The players obey the topological condition that all claimed vertices stay connected. The goal is to decide which player claims the majority of the vertices at the end of the play. We study greedy, symmetric and optimal strategies. We solve the topological network-control games on various classes of graphs. This progresses our understanding of combinatorial games played on graphs. We prove that finding an optimal winning strategy is a PSPACE-complete problem.
Recommended citation: Liang, Z., Khoussainov, B., Yang, H. (2024). Topological Network-Control Games. In: Wu, W., Tong, G. (eds) Computing and Combinatorics. COCOON 2023. Lecture Notes in Computer Science, vol 14423. Springer, Cham. https://doi.org/10.1007/978-3-031-49193-1_11
Download Paper