On Circuit Imbalance and 0/1 Circuits for Coloring and Forest Problems

Abstract

Circuits are fundamental objects in linear programming and oriented matroid theory, representing the elementary difference vectors of a polyhedron. A recent concept introduced by Dadush, Huiberts, Natura, and Végh, the circuit imbalance, serves as a complexity measure relevant to iteration bounds for circuit-based augmentation and circuit diameters, and the interpretability of circuits in terms of the underlying application. In this paper, we analyze linear programming formulations of relaxed combinatorial optimization problems to prove two contrasting types of results related to the circuit imbalance. First, we identify simple and polynomially-sized constraint structures, in particular arising in graph-theoretic problems, that lead to an exponential circuit imbalance. These constructions show that, in quite general situations, working with the entire set of circuits poses significant challenges for an application of circuit augmentation or the study of circuit diameters, even with a compact description of the underlying polytope. Second, through a case study of two classic graph-theoretic problems with exponential imbalance, the vertex graph coloring problem and the maximum weight forest problem, we exhibit the existence of sets of highly interpretable circuits within the set of 0/1 circuits of (best-case) imbalance 1. We prove that a restriction of circuit walks to these sets suffices to not only guarantee reachability of the integral extreme-points, but leads to a linear bound to walk between integral extreme-points for the fractional coloring polytope and a constant circuit diameter bound for the forest polytope, respectively. We conclude with a brief discussion of more general questions arising naturally from the use of 0/1 circuits in reachability and diameter studies.

arXiv commentstreamlining and corrections