Graph Sharing Games: Complexity and Connectivity

摘要

We study the following combinatorial game played by two players, Alice and Bob. Given a connected graph G with nonnegative weights assigned to its vertices, the players alternately take one vertex of G in each turn. The first turn is Alice's. The vertices are to be taken according to one (or both) of the following two rules: (T) the subgraph of G induced by the taken vertices is connected during the whole game, (R) the subgraph of G induced by the remaining vertices is connected during the whole game. We show that under all the three combinations of rules (T) and (R), for every ε > 0 and for every k > 1 there is a k-connected graph G for which Bob has a strategy to obtain (1 — ε) of the total weight of the vertices. This contrasts with the game played on a cycle, where Alice is known to have a strategy to obtain 4/9 of the total weight. We show that the problem of deciding whether Alice has a winning strategy (i.e., a strategy to obtain more than half of the total weight) is PSPACE-complete if condition (R) or both conditions (T) and (R) are required. We also consider a variation of the game where the first player who violates condition (T) or (R) loses the game. We show that deciding who has the winning strategy is PSPACE-complete.