We study the problem of optimizing an arbitrary weight function $w^Tz$ over the metric polytope of a graph $G=(V,E)$, a well-known relaxation of the cut polytope. We define the signed graph $(G, E^-)$, where $E^-$ consists of the edges of $G$ having negative weight. We characterize the sign patterns of the weight vector $w$ such that all optimal vertices of the metric polytope are integral, and we show that they correspond to signed graphs with no odd-$K_5$ minor. Our result has significant implications for unconstrained zero-one quadratic programming problems. We relate the strength of the cycle relaxation of the boolean quadric polytope to the sign pattern of the objective function. In this case, the sign patterns such that all optimal vertices of the cycle relaxation are integral correspond to signed graphs with no odd-$K_4$ minor.

We investigate new class of congestion games, called Totally Unimodular (TU) Congestion Games, where the players’ strategies are binary vectors inside polyhedra defined by totally unimodular constraint matrices. Network congestion games belong to this class. In the symmetric case, when all players have the same strategy set, we design an algorithm that finds an optimal aggregated strategy and then decomposes it into the single players’ strategies. This approach yields strongly polynomial-time algorithms to (i) find a pure Nash equilibrium, and (ii) compute a socially optimal state, if the delay functions are weakly convex. We also show how this technique can be extended to matroid congestion games. We then introduce some combinatorial TU congestion games, where the players'strategies are matchings, vertex covers, edge covers, and stable sets of a given bipartite graph. In the asymmetric case, we show that for these games (i) it is PLS-complete to find a pure Nash equilibrium even in case of linear delay functions, and (ii) it is NP-hard to compute a socially optimal state, even in case of weakly convex delay functions.