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? This paper shows that this is strongly co-NP-complete even in the case that the two base polyhedra are defined by cut capacity functions coming from two networks on the same set of nodes. This implies that (unless P = NP) there can be no polynomial algorithm for a problem in dynamic games that asks for a min-cost network that can ‘counter’ any move in a given network.