Simple algorithm finds paths through graph configurations efficiently
A simple algorithm for computing Hamilton paths on independent set polytopes
Discrete Mathematics
Summary
The paper presents a straightforward method to list all independent sets—groups of vertices without connected pairs—in a graph so that each step changes the group slightly. This approach avoids complex calculations and works fast, changing one vertex at a time or swapping a vertex with its neighbors. The method also extends to matchings in graphs and structures called posets, listing all relevant sets efficiently. The authors build on a general framework but simplify it by using a greedy, combinatorial rule.
What this means in practice
- •For graph algorithm developers: Generate all matchings of a graph efficiently with minimal changes between consecutive outputs.
- •For software engineers working with poset data: Enumerate all antichains or ideals of a poset quickly by changes limited to star-shaped differences.
Authors
Jean Cardinal, Pia Herkenrath, Torsten Mütze, Francesco Verciani
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 $\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.