Topological network-control games
Published in Theoretical Computer Science, 2026
The paper studies 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 solve these games on various classes of graphs such as linear forests and unions of cycles. This progresses our understanding of combinatorial games played on graphs.
Recommended citation: Zihui Liang, Bakh Khoussainov, Haidong Yang, Topological network-control games, Theoretical Computer Science, 2026, 115793, ISSN 0304-3975, https://doi.org/10.1016/j.tcs.2026.115793.
Download Paper