Faster and simpler traversal of 0/1-polytopes
Abstract
Recently, Merino and Mütze (FOCS'23+SICOMP'24) presented an algorithm for computing a Hamilton path on the skeleton of any 0/1-polytope conv(X), where X⊆{0,1}n. The algorithm uses as a black box an algorithm for solving the classical linear optimization problem min{w· x| x∈ X} for some weight vector w∈ℝn. The resulting delay per visited vertex on the Hamilton path is only by a log n factor larger than the time to solve one instance of the optimization algorithm. In this paper, we make the Hamilton path algorithm simpler and faster. Namely, we obtain an amortized delay that is only by a constant factor larger than the running time of the optimization algorithm, thus removing the log n factor. As concrete results, this yields improved algorithms for generating bases and independent sets in a matroid, spanning trees, forests, matchings and maximum matchings in a graph, vertex covers, minimum vertex covers, independent sets and maximum independent sets in a bipartite graph, and antichains, maximum antichains and ideals in a poset. All of these listings correspond to Hamilton paths on the corresponding polytopes. Furthermore, we obtain an 𝒪(tLP) amortized delay algorithm for the vertex enumeration problem on 0/1-polytopes {x∈ℝn| Ax≤ b}, where A∈ ℝm× n and b∈ℝm, and tLP is the time needed to solve the linear program min{w· x| Ax≤ b}. This improves upon the 𝒪(tLP log n) delay algorithm of Merino and Mütze, and the previous 𝒪(tLP n) delay algorithm of Bussieck and Lübbecke from 1998.
Related
- A simpler proof that there are no Landau--Siegel zeros
- A simpler proof of the Matrix Spencer Theorem
- Rayleigh's conjecture for vibrating plates: simpler planar proof and nonlinear extensions
- Context-Guided Traversal with Deep Reinforcement Learning for Suspicious Subgraph Detection in Cryptocurrency Transaction Graphs
- GORENSTEIN FANO POLYTOPES ARISING FROM ORDER POLYTOPES AND CHAIN POLYTOPES
BibTeX
@misc{fink2026faster,
title = {{Faster and simpler traversal of 0/1-polytopes}},
author = {Jiří Fink and Petr Hladík and Arturo Merino and Ondřej Mička and Torsten Mütze},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2607.17590},
eprint = {2607.17590},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.17590},
}
RIS
TY - UNPB
TI - Faster and simpler traversal of 0/1-polytopes
AU - Jiří Fink
AU - Petr Hladík
AU - Arturo Merino
AU - Ondřej Mička
AU - Torsten Mütze
PY - 2026
DA - 2026/10/09
PB - arXiv
DO - 10.48550/arxiv.2607.17590
UR - https://arxiv.org/abs/2607.17590
AB - Recently, Merino and Mütze (FOCS'23+SICOMP'24) presented an algorithm for computing a Hamilton path on the skeleton of any 0/1-polytope conv(X), where X⊆{0,1}^n. The algorithm uses as a black box an algorithm for solving the classical linear optimization problem min{w· x| x∈ X} for some weight vector w∈ℝ^n. The resulting delay per visited vertex on the Hamilton path is only by a log n factor larger than the time to solve one instance of the optimization algorithm. In this paper, we make the Hamilton path algorithm simpler and faster. Namely, we obtain an amortized delay that is only by a constant factor larger than the running time of the optimization algorithm, thus removing the log n factor. As concrete results, this yields improved algorithms for generating bases and independent sets in a matroid, spanning trees, forests, matchings and maximum matchings in a graph, vertex covers, minimum vertex covers, independent sets and maximum independent sets in a bipartite graph, and antichains, maximum antichains and ideals in a poset. All of these listings correspond to Hamilton paths on the corresponding polytopes. Furthermore, we obtain an 𝒪(t_LP) amortized delay algorithm for the vertex enumeration problem on 0/1-polytopes {x∈ℝ^n| Ax≤ b}, where A∈ ℝ^m× n and b∈ℝ^m, and t_LP is the time needed to solve the linear program min{w· x| Ax≤ b}. This improves upon the 𝒪(t_LP log n) delay algorithm of Merino and Mütze, and the previous 𝒪(t_LP n) delay algorithm of Bussieck and Lübbecke from 1998.
ER -