A simple algorithm for computing Hamilton paths on independent set polytopes
Abstract
The independent set polytope, or stable set polytope, of a graph G is the 0/1-polytope defined by the convex hull of the characteristic vectors of all independent sets of G. We present a simple algorithm for computing a Hamilton path on the independent set polytope of a given n-vertex graph G with amortized delay 𝒪(n). The independent sets are listed such that two consecutive sets differ either in removing a vertex, or adding a vertex and removing its neighbors from the independent set, i.e., the symmetric difference between two consecutive independent sets induces a star in G. As applications of this result, we obtain an algorithm to compute a Hamilton path on the matching polytope of an m-edge graph G with worst-case delay 𝒪(m), which lists all matchings of G in such a way that the symmetric difference between two consecutive matchings is a path on at most three edges. Furthermore, we obtain an algorithm to compute a Hamilton path on the chain polytope and order polytope of an n-element poset P with amortized delay 𝒪(n), which lists all antichains of P or all ideals of P, respectively, by star exchanges. Our algorithms are derived from the generic framework proposed by Merino and Mütze (FOCS'23+SICOMP'24) for computing Hamilton paths on arbitrary 0/1-polytopes, which uses a linear optimization procedure as a black box. Our algorithms bypass solving the computationally intractable maximum weight independent set problem by a simple and purely combinatorial greedy rule.
Related
- On the Minimum Number of Hamilton Cycles in Hamiltonian Threshold Graphs: A Simple Proof
- Computing key rates for one-sided device-independent quantum key distribution
- A simple stability analysis of the Lanczos algorithm in finite precision arithmetic
- A simple method of computing Riemann-type integrals
- An Efficient Symbolic Algorithm for Computing Lyapunov Constants in Planar Switching Systems
BibTeX
@misc{cardinal2026simple,
title = {{A simple algorithm for computing Hamilton paths on independent set polytopes}},
author = {Jean Cardinal and Pia Herkenrath and Torsten Mütze and Francesco Verciani},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.07304},
eprint = {2609.07304},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.07304},
}
RIS
TY - UNPB
TI - A simple algorithm for computing Hamilton paths on independent set polytopes
AU - Jean Cardinal
AU - Pia Herkenrath
AU - Torsten Mütze
AU - Francesco Verciani
PY - 2026
DA - 2026/10/09
PB - arXiv
DO - 10.48550/arxiv.2609.07304
UR - https://arxiv.org/abs/2609.07304
AB - The independent set polytope, or stable set polytope, of a graph G is the 0/1-polytope defined by the convex hull of the characteristic vectors of all independent sets of G. We present a simple algorithm for computing a Hamilton path on the independent set polytope of a given n-vertex graph G with amortized delay 𝒪(n). The independent sets are listed such that two consecutive sets differ either in removing a vertex, or adding a vertex and removing its neighbors from the independent set, i.e., the symmetric difference between two consecutive independent sets induces a star in G. As applications of this result, we obtain an algorithm to compute a Hamilton path on the matching polytope of an m-edge graph G with worst-case delay 𝒪(m), which lists all matchings of G in such a way that the symmetric difference between two consecutive matchings is a path on at most three edges. Furthermore, we obtain an algorithm to compute a Hamilton path on the chain polytope and order polytope of an n-element poset P with amortized delay 𝒪(n), which lists all antichains of P or all ideals of P, respectively, by star exchanges. Our algorithms are derived from the generic framework proposed by Merino and Mütze (FOCS'23+SICOMP'24) for computing Hamilton paths on arbitrary 0/1-polytopes, which uses a linear optimization procedure as a black box. Our algorithms bypass solving the computationally intractable maximum weight independent set problem by a simple and purely combinatorial greedy rule.
ER -