Source-linked AI summary
A simple algorithm for computing Hamilton paths on independent set polytopes
Jean Cardinal, Pia Herkenrath, Torsten Mütze, Francesco Verciani
TL;DR
Independent-set polytopes pose a Hamilton-path enumeration problem for which generic methods rely on hard optimization. This paper gives a purely combinatorial algorithm using star exchanges, with amortized O(n) delay, and applies it to matching and poset polytopes.
Problem
The task is to list every independent set exactly once along a Hamilton path, although the generic polytope framework relies on optimization that is hard for independent sets.
Source: §1 · p. 2, §1.1 · p. 3Method
A purely combinatorial algorithm uses star exchanges to compute Hamilton paths from any initial independent set without solving the corresponding hard optimization problem.
Source: §1.2 · p. 3Results
The independent-set listing has amortized O(n) delay, while matching-polytope listings have worst-case O(m) delay and chain- and order-polytope listings have amortized O(n) delay.
Source: §1.2 · pp. 3–4Takeaways & Limitations
Star exchanges yield Hamilton paths for independent-set, matching, chain, and order polytopes, with consecutive matching differences forming paths of at most three edges.
Source: §1.2 · pp. 3–4
Abstract
from arXiv · showhide
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\"utze (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.
1. Introduction
The introduction frames Hamilton-path enumeration of independent sets as a difficult 0/1-polytope problem and presents a combinatorial algorithm with star exchanges. It also situates the method among related enumeration algorithms and applications to matchings and posets.
1. Introduction.
- The independent set polytope is the convex hull of independent-set characteristic vectors; matchings are independent sets in the line graph, but maximum-weight matching is tractable while independent-set optimization is NP-hard.The matching polytope of G equals the independent set polytope of L(G).Source: §1 · pp. 1–2
1.1. Hamilton paths on 0/1-polytopes.
- Independent-set Hamilton paths require consecutive sets whose symmetric difference induces a connected subgraph, while the generic 0/1-polytope approach relies on an optimization oracle that is hard for P(G).The paper seeks an efficient listing that visits every independent set exactly once.Source: §1.1 · pp. 2–3
1.2. Our results.
- The algorithm computes a Hamilton path on P(G) for any graph and labeling, from any initial independent set, using star exchanges with amortized delay O(n).It is purely combinatorial and avoids solving the corresponding hard optimization problem; the resulting ordering also has the genlex property.Source: §1.2 · p. 3
- The applications include matching-polytope paths with worst-case delay O(m), and chain- and order-polytope paths listing antichains and ideals with amortized delay O(n).Consecutive matchings differ along an alternating path of at most three edges; the poset listings use star exchanges.Source: §1.2 · pp. 3–4
1.3. Related work.
- Prior work lists inclusion-maximal independent sets with delay O(mn); separate results address maximum independent sets of bipartite graphs and their associated polytopes.The paper notes that maximum independent set is NP-hard in general graphs.Source: §1.3 · p. 4
- Merino and Mütze [MM24] gave Hamilton-path algorithms for matching and perfect-matching polytopes with delays O(m√n) and O(m√n log n); this paper improves matching-polytope delay to O(m).For chain and order polytopes, [MM24] gives delays O(n^2.5/√log n) and O(n^4), respectively; this paper reports amortized delay O(n).Source: §1.3 · p. 4
- Prior ideal listings include 1- and 2-Gray codes, but Gray codes of width at least two are generally not Hamilton paths on the associated polytopes.A recent algorithm lists ideals and antichains in 3-Gray-code order with amortized delay O(1), but these listings are generally not polytope Hamilton paths.Source: §1.3 · pp. 4–5
1.4. Outline.
- The paper presents the basic and improved algorithms in Section 2, their applications in Section 3, and an experimental comparison on varied graphs in Section 4.Source: §1.4 · p. 5
2. The algorithm
The algorithms recursively list every independent set along a Hamilton path, using star exchanges between consecutive sets. Algorithm I* preserves Algorithm I’s path while reducing its amortized delay to O(n).
2.1. Preliminaries.
- The independent-set polytope is the convex hull of characteristic vectors of independent sets, and two such vertices are adjacent exactly when their symmetric difference induces a connected subgraph.Source: §2.1 · pp. 5–6
- A star exchange removes one vertex or adds one vertex while removing its neighbors; each such transition is a polytope edge, though not every edge is a star exchange.Source: §2.1 · p. 6
2.2. Basic algorithm.
- Algorithm I greedily changes the shortest eligible prefix, using an auxiliary bit array to avoid revisiting independent sets and produce a genlex Hamilton path.The array marks suffixes whose independent sets have already been visited; transitions are star exchanges.Source: §2.2 · pp. 6–7
- Algorithm I works for every graph and initial independent set, with star exchanges and worst-case delay O(n(d>(G) + 1)).This is also bounded by O(n(∆(G) + 1)) and O(n^2).Source: §2.2 · p. 7
- Vertex labeling affects the delay bounds: Algorithm I benefits from small forward degeneracy, while Algorithm I* benefits from small backward degeneracy.For Algorithm I, bounded degeneracy gives linear delay; Algorithm I* has linear amortized delay regardless of graph degrees.Source: §2.2 · p. 7, §2.3 · p. 10
2.3. Improved algorithm.
- Algorithm I* stores counts of selected larger neighbors to find eligible prefixes in linear time, and amortizes its update loop to O(n) per iteration.The update analysis prepays work for smaller-neighbor edges when vertices are added.Source: §2.3 · pp. 9–10
- O(n) amortized delay, with worst-case O(n + d<(G)^2), is achieved by Algorithm I* for every graph and initial independent set.It computes the same Hamilton path as Algorithm I; its initialization takes O(m) time.Source: §2.3 · p. 10
3. Applications
The algorithms recover familiar Gray codes and extend Hamilton-path listings to vertex covers, matchings, antichains, and ideals. These applications retain local exchanges, with delay bounds of O(m) for matchings and amortized O(n) for posets.
3.1. Independent sets of special families of graphs.
- On empty graphs the algorithms produce the binary reflected Gray code, while paths and qualifying cycles yield Fibonacci and Lucas word Gray codes.For paths and cycles Cn with 3 not dividing n, the codes start at [010]n and end at [001]n.Source: §3.1 · pp. 10–12
- Complementing each independent set yields a Hamilton path on the vertex-cover polytope, with consecutive covers differing by a complemented star exchange.Each step adds one vertex to the cover, or removes one vertex and adds its neighbors.Source: §3.2 · p. 12
3.3. Matchings.
- Algorithm M lists every matching along a genlex Hamilton path with worst-case delay O(m), and consecutive matchings differ by a {1, 2, 3}-exchange.Such an exchange removes one edge, or adds an edge while removing at most two incident matching edges.Source: §3.3 · p. 13
3.4. Antichains and ideals.
- Algorithm A* gives a genlex Hamilton path on the chain polytope with amortized delay O(n), joining antichains by star exchanges.An antichain transition removes one element or adds an element while removing its proper downset.Source: §3.4 · pp. 14–15
- The poset applications use the antichain–ideal correspondence to translate antichain listings into ideal listings.For the order-polytope listing, the algorithm stores the current ideal while doing its computations on the corresponding antichain.Source: §3.4 · pp. 15–16
- The modified Algorithm A* gives a genlex Hamilton path on the order polytope with amortized delay O(n), joining ideals by star exchanges.The algorithm follows the corresponding antichains and computes their ideals along the way.Source: §3.4 · p. 16
4. Experimental comparison of Algorithms I and I*
The experiments compare Algorithms I and I* across graph families and vertex orderings using array accesses as a proxy for work. They find that I* generally benefits from increasing average degree, while ordering choices substantially affect performance.
4. Experimental comparison of Algorithms I and I*
- The evaluation measures D/n using read and write accesses to algorithm arrays, and plots it against graph average degree.Figure 7 separates sparse and dense graphs into columns and places Algorithms I and I* in the top and bottom rows.Source: §4 · pp. 16–17, Figure 7 · p. 18
4.1. Evaluation.
- As average degree grows, Algorithm I* maintains constant average delay per bit, while Algorithm I’s average delay per bit grows linearly.The authors report that I* is faster on all but the smallest and sparsest graphs; Figure 7 compares the algorithms across input graphs.Source: §4.1 · p. 17, Figure 7 · p. 18
- For very sparse graphs, average delay per bit decreases as vertex count grows because most changes occur on short prefixes.For empty graphs, average prefix length in the binary reflected Gray code is 2 − o(1), so average delay is constant.Source: §4.1 · p. 17
- For Algorithm I on dense tripartite and random graphs, min ordering is fastest and max is slowest, with the gap growing with average degree.The reported orderings also include revmin, revmax, and averages over ten random orderings.Source: §4 · p. 17, §4.1 · p. 18
- On irregular complete tripartite graphs, Algorithm I* runs approximately twice as fast with min ordering as with revmin ordering.The authors explain that small-label vertices are examined more often and argue that min ordering is preferable in practice for both algorithms.Source: §4.1 · pp. 18–19