Papers for

software engineers working with poset data

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Simple algorithm finds paths through graph configurations efficiently

A simple algorithm for computing Hamilton paths on independent set polytopes

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.

Mon 7 SeptDiscrete Mathematics
The gist
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.
Open → 2609.07304v1