CS Paper Radar

Generating pivot Gray codes for spanning arborescences of complete digraphs and split digraphs in constant amortized time

Bowie Liu, Dennis Wong

cs.DS ·submitted 2026-10-27 18:04 UTC · v1

Abstract

We present the first known efficient algorithm to generate pivot Gray codes for spanning arborescences of complete digraphs, listing all spanning arborescences such that consecutive arborescences differ by reassigning the outgoing edge of exactly one vertex. Our recursive algorithm generates each spanning arborescence in constant amortized time using $O(n^2)$ space. We then extend our algorithm to generate the first known pivot Gray codes for spanning arborescences of split digraphs, achieving constant amortized time per arborescence using $ O(n^2) $ space. Finally, we further generalize our approach to proper interval digraphs. When the arborescences are rooted at the leftmost interval, our algorithm generates the pivot Gray code in constant amortized time per arborescence using $ {O}(n^2) $ space.

Closest papers

Nearest neighbours by meaning across the whole index.

Generating cyclic pivot Gray codes for well-ordered $k$-degenerate graphs in constant amortized time

cs.DS ·2026-10-07 ·Lei Dong, Dennis Wong, Bowie Liu, Rui Bao, Lin Chen +2 more
similarity 0.75
Abstract · 38 pages, 4 figures

A graph $G$ is $k$-degenerate if there exists an ordering $v_1, v_2, \dots, v_n$ of its vertices such that each vertex $v_i$ has at most $k$ neighbors $v_j$ in $G$ with $j < i$. A well-ordered $k$-degenerate graph is a labeled graph on the vertex set $\{1, 2, \dots, n\}$ in which every vertex $i$ has at most $k$ neighbors among $1, 2, \dots, i-1$. We present the first simple algorithms that generate, rank, and unrank cyclic pivot Gray codes for well-ordered $k$-degenerate graphs, where consecutive graphs differ by the addition, removal, or pivoting of a single edge. Our algorithm generates each well-ordered $k$-degenerate graph in constant amortized time per graph, using $O(n^2)$ space, while ranking and unranking take $O(n^2)$ time and $O(n^2)$ space.

0.30

Constructive Arboricity in Almost-Linear Time for Dense Graphs

cs.DS ·2026-10-09 ·Iman Gholami, Mohammad T. Hajiaghayi, Mahdi JafariRaviz, Alireza Kaviani, Soheil Mohammadkhani +1 more
similarity 0.63
Abstract

The arboricity of a graph is the minimum number of forests needed to partition its edges. We present an algorithm that computes the exact arboricity of a simple graph and constructs an optimal forest partition in $\min\{n^{2+o(1)},m^{4/3+o(1)}\}$ time, where $n$ and $m$ denote the numbers of vertices and edges. This improves the previous $O(m^{3/2}\log(n^2/m))$ bound of Gabow. In particular, it runs in almost-linear time, $m^{1+o(1)}$, on dense graphs with $m=Θ(n^2)$. We also give an algorithm that constructs a partition into at most one more forest than optimal in $m^{1+o(1)}$ time. To our knowledge, it is the first almost-linear time algorithm for this problem.

0.22

Dynamic Edge Orientation via Random Walks: From Trees to Outerplanar Graphs and Beyond

cs.DS ·2026-08-25 ·Gabriel Marques Domingues, Minh Hang Nguyen, Shay Solomon
theory similarity 0.61
Abstract · Abstract truncated to fit arXiv limits

We study the \emph{fully dynamic edge orientation problem}, focusing on \emph{worst-case} time bounds. An undirected graph undergoes edge insertions and deletions, and the goal is to maintain an orientation with small {\em maximum outdegree} (hereafter, outdegree) and small worst-case update time. The outdegree of any orientation is at least $α-1$, where $α$ is the graph's \emph{arboricity}, i.e., the minimum number of forests into which its edge set can be partitioned. When $α= O(1)$, it is long known that both the outdegree and the worst-case update time can be bounded by $O(\log n)$. Despite numerous follow-ups, no $o(\log^3 n)$ worst-case update time is known for maintaining constant outdegree, even for very basic graph families---with a notable exception, \emph{forests}. For forests, a \emph{simple folklore} algorithm maintains outdegree 2 via \emph{random walks}: When an insertion creates a vertex of outdegree 3, the algorithm repeatedly chooses a uniformly random outgoing edge until reaching a vertex of outdegree at most 1, and then flips the resulting directed path. As the underlying graph is cycle-free, the path length is easily shown to be $O(\log n)$ in expectation, and also with high probability for polynomially long update sequences. We prove that this simple random walk paradigm extends to \emph{outerplanar graphs}. Our algorithm maintains constant outdegree with $O(\log n)$ worst-case update time, where the time bound holds in expectation, and also with high probability for polynomially long update sequences. We give a \emph{tight analysis}: outdegree 4 is achievable with $O(\log n)$-length paths, while outdegree 3 incurs $\mathtt{poly}(n)$-length paths. We also extend the argument to $K_{2,t}$-minor-free graphs, for any $t \ge 2$, with the outdegree bound depending only on $t$ and with the same update time guarantees. The locality of [...]

0.27

Dynamic Edge Orientation on Low-Arboricity Graphs: Breaking the $\log n$ Barrier

cs.DS ·2026-11-06 ·Sam Hiken, Nicole Wein
theory similarity 0.60
Abstract · 29 pages, 3 figures

We study the dynamic edge orientation problem introduced in a seminal 1999 paper by Brodal and Fagerberg: given a fully dynamic graph $G$ with arboricity bounded by $α$, maintain an orientation on $G$'s edges so every vertex has out-degree upper bounded by a function of $α$. They provided an algorithm with $O(α+ \log n)$ amortized update time that maintains an orientation with maximum out-degree $O(α)$. In the decades since, this algorithm has found widespread applications in dynamic graph algorithms. Nevertheless, it has remained a stubborn open question whether, when $α= o(\log n)$, the $O(\log n)$ upper bound can be improved. We answer this 27-year-old question in the affirmative, showing that Brodal and Fagerberg's algorithm for maintaining an out-degree $O(α)$ orientation runs in $O(α\cdot \log \log n)$ amortized update time, which is an exponentially-improved dependence on $n$. This is the first improvement on Brodal and Fagerberg's upper bound even for the $α=1$ case of dynamic forests. Our crucial technical innovation is to construct a hierarchy of dynamic graphs with a property we call near isolation. We believe that this construction may be useful for related problems.

0.24

Single-Exponential Algorithms for Directed Feedback Vertex Set on Planar Digraphs

cs.DS ·2026-09-26 ·Daniel Lokshtanov, Saket Saurabh, Jie Xue
theory similarity 0.59
Abstract

We consider Directed Feedback Vertex Set on planar digraphs, parameterized by the solution size $k$. We give a randomized algorithm with one-sided error running in time $(2+\sqrt5)^k n^{O(1)}= 4.24^k n^{O(1)}$, and a deterministic algorithm running in time $8.04^k n^{O(1)}$. Both algorithms use polynomial space. To the best of our knowledge, these are the first single-exponential fixed-parameter algorithms for Directed Feedback Vertex Set on planar digraphs. This contrasts with general digraphs, where the best known algorithms run in time $2^{O(k\log k)}(n+m)$, and whether a $2^{o(k\log k)}n^{O(1)}$-time algorithm exists remains a major open problem. Our main tool is an exact Euler-type counting identity for plane digraphs. It shows that every small solution must carry a large share of the vertices whose in- and out-arcs alternate in the embedding, while solutions avoiding such vertices can be computed by reducing to Directed Feedback Arc Set, which is known to be solvable in polynomial time on planar digraphs via the Lucchesi-Younger theorem.

0.38

Directed Global Minimum Cut in Almost-Linear Time

cs.DS ·2026-10-07 ·Henry Fleischmann, Jason Li, Thatchaphol Saranurak, Benyu Wang
highly cited similarity 0.59
Abstract · 11 pages, 4 figures

We give a randomized reduction from global minimum cut in a directed graph with $n$ vertices and $m$ weighted edges to maximum-flow computations on graphs of total size $\widetilde{O}(m)$. For polynomially bounded integral weights, this yields the first almost-linear $m^{1+o(1)}$-time algorithm [vdBCK+23], improving the previous $m^{1+o(1)}\min\{\sqrt{n},n/m^{1/3}\}$ bound [CLN+22]. Previous work reduced finding the minimum cut to constructing a 1-respecting arborescence, a directed spanning tree with exactly one edge crossing a minimum cut [CLN+22]. They then construct such a tree by sampling from a $(1+ε)$-approximate arborescence packing, which currently requires superlinear time. Our algorithm sidesteps constructing the packing entirely and relies on a novel iterative arborescence sampling procedure. We show that, after $O(\log n)$ rounds of sampling, our final arborescence 1-respects the minimum cut with constant probability.

0.48

Minimum-Cost $k$-Arborescence Packing in $\tilde O(km+k^4 n)$ Time

cs.DS ·2026-11-05 ·Zhaienhe Zhou
similarity 0.58
Abstract

We give a deterministic, strongly polynomial algorithm running in $\tilde{O}(km+k^4n)$ time that finds $k$ arc-disjoint arborescences of minimum total cost in a directed multigraph with $n$ vertices and $m$ arcs. This significantly improves upon the state of the art for $k \ge 2$ with $k=n^{o(1)}$: the prior fastest weakly polynomial and strongly polynomial algorithms take $\tilde{O}(km\sqrt{n}\log C)$ and $\tilde{O}(kmn)$ time (Gabow and Xu, 1989; Gabow, 1995), respectively. Roughly, our technique can be viewed as a way to apply a linear number of \emph{shortest} augmenting paths in near-linear total time for the special case of the weighted matroid intersection problem between the $k$-fold graphic matroid and the indegree partition matroid. This was previously done in the unweighted case by Gabow (1995), but our approach is different. As an extension, we also obtain a deterministic $\tilde{O}(km^{1+o(1)}+k^5n)$-time algorithm for minimum-cost maximum-cardinality packing of $k$ forests in undirected graphs. In particular, this finds $k$ edge-disjoint spanning trees of minimum total cost, if they exist. The previous fastest algorithm takes $\tilde{O}(kn^2+m)$ time (Gabow and Westermann, 1992).

0.23

Four-Coloring Planar Graphs in Linear Time

cs.DS cs.CGcs.DMmath.CO ·2026-10-29 ·Yuta Inoue, Ken-ichi Kawarabayashi, Atsuyuki Miyashita, Bojan Mohar, Carsten Thomassen +1 more
theoryhot direction similarity 0.58
Abstract

The famous Four Color Theorem (4CT) states that any planar graph can be colored with four colors, but how do we find a 4-coloring? In our previous paper [FOCS'26], we presented a simple combinatorial algorithm to 4-color planar graphs in $O(n\log n)$ time. We improve it here to $O(n)$ time, which is optimal. The algorithm from our previous paper is based on proving that every planar triangulation has a linear number of reducible configurations or obstructing cycles. The bottleneck for the algorithm is that we need $O(\log n)$ Kempe changes to extend a recursive 4-coloring to the reducible configurations. Each Kempe change can involve a constant fraction of the graph and takes linear time. Here we show that all $O(\log n)$ Kempe changes can be identified and implemented in $O(n)$ time. The idea is to spend $O(n)$ time to preprocess the graph so that we can identify and simulate each good Kempe change in $O(n/\log n)$ amortized time. Thus, we implement all $O(\log n)$ Kempe changes in $O(n)$ total time. Based on this, we implement the whole 4-coloring in linear time. We note that creating such a representation for fast identification and simulation of the right Kempe changes is a challenge of data structures, unlike the previous paper that builds on a new graph theoretic understanding of reducible configurations.

0.22