Haidong Yang: Topological network-control games

Abstract

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.