SUBMODULAR CONTAINMENT IS HARD, EVEN FOR NETWORKS

Suppose that we have two submodular base polyhedra in the same space. What is the complexity of deciding if one is contained in the other? T his paper shows that this is strongly co-NP-complete even in the case that the two base polyhedra are defined by cut capacity functions comi ng from two networks on the same set of nodes. This implies that (unle ss P = NP) there can be no polynomial algorithm for a problem in dynam ic games that asks for a min-cost network that can ''counter'' any mov e in a given network.