On Some Spanning Tree Games

We investigate four games related to spanning trees in a graph. First we study a two-person zero-sum game where an evader every few minutes chooses a spanning tree in a network and sends a signal. Then an inspector also every few minutes chooses an edge to inspect. The evader needs a tree selection strategy that minimizes the average probability of being detected. The inspector seeks to maximize this probability. We show that finding the evader’s optimal strategy reduces to finding a maximum packing of spanning trees, and finding the inspector’s strategy reduces to computing the strength of a graph. Then we treat another game where an attacker chooses a set of edges to destroy, and an inspector chooses an edge to find the attacker. We show that finding the inspector’s strategy reduces to finding a minimum spanning tree, and the attacker strategy is given by a maximum packing of partitions of the node-set.

Then we study two cooperative games in a graph. In the first game each coalition corresponds to a set S of edges, and the value of it is the maximum number of disjoint spanning trees included in S. In the second game each coalition also corresponds to a set of edges S, and the value of the coalition is the number of new connected components created after removing the edges in S. For these two games we show that testing whether the core is non-empty, finding an element of the core, and testing membership to the core can be done in polynomial time.