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.

By: Mourad Baïou, Francisco Barahona

Published in: RC25566 in 2015


This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.


Questions about this service can be mailed to reports@us.ibm.com .