{"id":"arxiv/2609.07304","url":"https://arxiv.org/abs/2609.07304","tags":["cs.DM","math.CO"],"score":0,"title":"A simple algorithm for computing Hamilton paths on independent set polytopes","domain":"cs.DM","source":"arxiv","authors":["Jean Cardinal","Pia Herkenrath","Torsten Mütze","Francesco Verciani"],"reviews":0,"subject":"cs.DM","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-07","reactions":{}}