Simple algorithm finds paths through complex graph structures efficiently
A simple algorithm for computing Hamilton paths on independent set polytopes
Discrete Mathematics
Summary
The problem is to list all independent sets of a graph so that each set differs from the next in a simple way. The authors created an easy algorithm that does this efficiently by only adding or removing a vertex in a specific manner, forming simple connections called stars. This method also applies to listing matchings in graphs and special subsets in ordered sets. Their approach uses a known framework but avoids hard optimization steps by relying on a straightforward rule. This makes the problem of exploring these complex graph structures more practical.
independent setgraphHamilton pathpolytopematchingposetantichainidealsymmetric differencealgorithm
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.