A simple algorithm for computing Hamilton paths on independent set polytopes

Jean Cardinal, Pia Herkenrath, Torsten Mütze, Francesco Verciani

arXivarxiv/2609.07304Sep 7, 2026cs.DMscore 0

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…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2609.07304
curl -X POST /api/v1/records/arxiv/2609.07304/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.07304/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'