Metraipolis › archive › dc_cae01682d214
A simple algorithm for computing Hamilton paths on independent set polytopes — arXiv:2609.07304
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.07304
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T14:49:21.591Z
- SHA-256 of the archived text
97a5b17d87a24928e37ff83461656000ca66486d589bda067e7adedc169e8f37- Stable URL of this page
https://metraipolis.com/documento/dc_cae01682d214
How to cite
A simple algorithm for computing Hamilton paths on independent set polytopes — arXiv:2609.07304 — arXiv (en), https://arxiv.org/abs/2609.07304 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_cae01682d214 (Metraipolis archive dc_cae01682d214, sha256 97a5b17d87a24928e37ff83461656000ca66486d589bda067e7adedc169e8f37)
BibTeX
@misc{dccae01682d214,
title = {A simple algorithm for computing Hamilton paths on independent set polytopes — arXiv:2609.07304},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.07304},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_cae01682d214; sha256 97a5b17d87a24928e37ff83461656000ca66486d589bda067e7adedc169e8f37},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.07304. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 $\mathcal{O}(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 $\mathcal{O}(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 $\mathcal{O}(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.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-09 in math.CO).
Categorie arXiv: Discrete Mathematics (cs.DM) ; Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2609.07304 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T14:32:29.928Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-09?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).