graph algorithm developers

Abstract: We study a graph simplification problem introduced by Bernstein, Bodwin, and Wein [ITCS'24]. We start with a graph with arbitrarily large positive edge weights and the goal is to reweight the edges to small aspect ratio (ratio between largest and smallest weight) while preserving the shortest paths structure (the sequence of vertices and edges along shortest paths). They studied whether polynomial aspect ratio is always possible. They proved that for general graphs, both directed and undirected, it is not: there exist graphs for which any shortest-paths preserving reweighting requires exponential aspect ratio. In contrast, they showed that every DAG (directed acyclic graph) admits a reweighting with linear aspect ratio. However, the resulting edge weights are not integers. This motivated them to pose the open question of whether all DAGs admit a reweighting with polynomially-bounded integer edge weights. Our main result is to answer this question in the negative: we prove that there exist DAGs for which any shortest-paths preserving integer reweighting requires weights of size $2^{Ω(n)}$. In fact, this is even true when the DAG has very simple structure: 3 layers of vertices with only 3 vertices in the middle layer. In contrast, we show that if the number of vertices in the middle layer is decreased to 2, then a linear upper bound is possible. We extend our exponential lower bound to the approximate version of the problem where only a single $α$-approximate shortest path in the original graph must be preserved as an exact shortest path in the reweighted graph. Our exponential lower bound holds even for any finite approximation ratio $α>1$.

Abstract: Let $λ$ be the minimum cut value of an $n$-vertex undirected multigraph. For every fixed $α>1$, we prove that there are $O(n^{\lceil2α\rceil-1})$ cuts of size strictly below $αλ$. The exponent is sharp. The proof combines splitting off and sampling with a bound on the size of nested families of vertex sets.

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.