On Circuit Imbalance and 0/1 Circuits for Coloring and Spanning Forest Problems
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915655726399488 |
|---|---|
| author | Borgwardt, Steffen Crawford, Nicholas Kafer, Sean Lee, Jon Morrison, Angela |
| author_facet | Borgwardt, Steffen Crawford, Nicholas Kafer, Sean Lee, Jon Morrison, Angela |
| contents | Circuits are fundamental objects in linear programming and oriented matroid theory, representing the elementary difference vectors of a polyhedron between points in its affine space. A recent concept introduced by Ekbatani, Natura, and Végh, the circuit imbalance, serves as a complexity measure relevant to iteration bounds for circuit-based augmentation and circuit diameters, as well as the general 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.
On one hand, we identify simple and common constraint structures, in particular arising in graph-theoretic problems, that inherently 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.
On the other hand, 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 and subsets of highly interpretable circuits of (best-case) imbalance 1. These sets correspond to the recoloring of vertices or to the addition or removal of edges, respectively, for example generalizing classic concepts of Kempe dynamics in coloring. Their interpretability in terms of the underlying application facilitates a study of circuit walks in the corresponding polytopes. We prove that a restriction of circuit walks to these sets suffices to not only guarantee reachability of the integral extreme-points of the skeleton, but leads to linear and constant circuit diameter bounds, respectively. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_05223 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On Circuit Imbalance and 0/1 Circuits for Coloring and Spanning Forest Problems Borgwardt, Steffen Crawford, Nicholas Kafer, Sean Lee, Jon Morrison, Angela Optimization and Control 05C69, 52B05, 90C05, 90C27 Circuits are fundamental objects in linear programming and oriented matroid theory, representing the elementary difference vectors of a polyhedron between points in its affine space. A recent concept introduced by Ekbatani, Natura, and Végh, the circuit imbalance, serves as a complexity measure relevant to iteration bounds for circuit-based augmentation and circuit diameters, as well as the general 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. On one hand, we identify simple and common constraint structures, in particular arising in graph-theoretic problems, that inherently 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. On the other hand, 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 and subsets of highly interpretable circuits of (best-case) imbalance 1. These sets correspond to the recoloring of vertices or to the addition or removal of edges, respectively, for example generalizing classic concepts of Kempe dynamics in coloring. Their interpretability in terms of the underlying application facilitates a study of circuit walks in the corresponding polytopes. We prove that a restriction of circuit walks to these sets suffices to not only guarantee reachability of the integral extreme-points of the skeleton, but leads to linear and constant circuit diameter bounds, respectively. |
| title | On Circuit Imbalance and 0/1 Circuits for Coloring and Spanning Forest Problems |
| topic | Optimization and Control 05C69, 52B05, 90C05, 90C27 |
| url | https://arxiv.org/abs/2512.05223 |