Speaker:

Zihui Liang (Ph.D. student in University of Electronic Science and Technology of China)

Time:

• 16:20-17:20 (Time in Beijing)
• 21:20-22:20 (Time in Auckland)
• March 18, 2022 (Friday)

Venue:

B1-518B, Research Building 4

Abstract:

We introduce new combinatorial games played on graphs that we call network-control games. These games model the influence of competing two parties aiming to control the network. In a network-control game, the players move alternatively on a given undirected graph. At each turn, a player selects an unclaimed vertex and its unclaimed neighbours within distance t. The goal is to decide which player claims most of the vertices. We study greedy strategies, symmetric strategies, and fully solve network-control games played on multilines, cycles and a special class of caterpillars. We develop a framework that reduces the sizes of graphs by preserving the winner of the original game. Some proofs involve computer assisted techniques. We study a relaxed version of the network-control games and prove that finding the winner in such games is a PSPACE-complete problem. We show that by changing the underlying graph slightly (by using quasi-isometries), the network-control game can be solved efficiently in the modified graph.