Jun 2026· arXiv.org· Vol abs/2606.31560· 1 citation· 44 references
Computer Science
TL;DR
This work shows that any directed graph with pathwidth $pw$ admits an $(O(\mathsf{pw}), \Delta)$-LDD, and improves upon the previous best-known $(2^{O(\mathsf{pw}^2)}, \Delta)$-LDD construction, which was implicitly derived from the quasipartition result of Salmasi, Sidiropoulos, and Sridhar [SODA'19].
Abstract
Low diameter decompositions, or LDDs for short, are a fundamental primitive in the design of efficient graph algorithms. Roughly speaking, an LDD is a distribution over partitions of the vertices into bounded-diameter clusters such that nearby vertices are likely to be clustered together. Recently, there has been growing interest in lifting the notion of LDDs into \emph{directed graphs}. In particular, there are two natural directed analogues. The first is a directed LDD, where after removing a random subset of edges, every strongly connected component has a small diameter. The second is a quasipartition, which imposes the stronger requirement that whenever one vertex can still reach another after the edge removal, the two vertices must be close in the original directed metric. Every quasipartition yields an LDD, but the converse does not necessarily hold. In this work, we initiate the systematic study of LDDs in structured directed graphs. As our first main result, we show that any directed graph with pathwidth $\mathsf{pw}$ admits an $(O(\mathsf{pw}), \Delta)$-LDD. This improves upon the previous best-known $(2^{O(\mathsf{pw}^2)}, \Delta)$-LDD construction, which was implicitly derived from the quasipartition result of Salmasi, Sidiropoulos, and Sridhar [SODA'19]. As our second result, we show that the integrality gap of the Directed Non-Bipartite Sparsest-Cut LP relaxation on an $n$-vertex graph with treewidth $\mathsf{tw}$ is $O(\mathsf{tw} \log n)$. This improves upon the $O(\mathsf{tw}\log^2 n)$ bound of M\'emoli, Sidiropoulos, and Sridhar [ICALP'16, Algorithmica'18]. We obtain this result through the refined analysis of the quasipartition construction of M\'emoli et al. for bounded treewidth graphs.
Let $\mathcal F$ be a graph class that is closed under topological minors and 1-sums, has decidable membership, contains a triangle, and is not the class of all graphs. Recently, Lee, Liu, and Tsai [ICALP 2026] showed that the edge-decomposition problem into $k \geq 3$ elements of $\mathcal F$ is NP-hard. In particular, their general hardness reduction covers a long-standing problem on outerthickness (when $\mathcal F$ is the class of outerplanar graphs). On the other hand, it is well known that decomposing a graph into forests is polynomial-time solvable, as implied by work of Edmonds [J. Res. Natl. Bur. Stand. B. 1965]. In this paper, we take a first step toward determining the complexity of edge-decomposition problems into just two graphs (the case $k=2$). We consider the simplest possible graph class $\mathcal F$ satisfying the criteria above: the triangular forests, that is, graphs in which every 2-connected component is a triangle. We prove that determining whether a graph can be edge-decomposed into two triangular forests is NP-complete.
A functional digraph is a directed graph where each vertex has an out-degree of at most 1. We study the number of successor-closed subsets of a functional digraph, that is, subsets from which no edge leaves, and show that this decomposition yields a simple recursive formula for the corresponding generating function. Using this formula, we determine, among all functional digraphs with a fixed number of vertices and edges, the one maximizing the number of successor-closed subsets of every size simultaneously. Somewhat unexpectedly, this extremal result yields a quantitative strengthening of the set-pairs inequality of Bollobas: rather than merely guaranteeing that some pair of a large enough family must violate the hypothesis of the theorem, we show that a uniformly random subset of the family witnesses a violation with high probability, quantitatively in terms of how far the family size exceeds the classical threshold. We further show that the same approach applies to the skew variant of Bollobas's inequality due to Hegedus and Frankl, yielding an analogous probabilistic strengthening.
We investigate metric dimension and the localization game for several families of directed analogues of strongly regular graphs and their generalizations, adapting a probabilistic method of Babai (1980) for bounding the size of resolving sets in undirected strongly regular graphs. We derive upper bounds on the localization number and metric dimension depending on the order of the graph and the maximum number of common out-neighbours for a pair of vertices. We consider normally regular digraphs, so-called"ordinary graphs", classes of Deza digraphs, divisible design digraphs, nearly doubly regular tournaments, and certain doubly regular team tournaments. In particular, for asymmetric normally regular digraphs on $n$ vertices, we show that these invariants are bounded above by $O(\sqrt{n} \log n)$, and improve this to $O(\log n)$ for a class of doubly regular team tournaments.
An ordered Ruzsa-Szemeredi graph is a graph whose edge set is partitioned into equal-size matchings, each induced in the suffix of the ordering that begins with it. Behnezhad and Ghafari introduced them to parametrize the update time of fully dynamic matching, but almost nothing is known about the numbers themselves. Writing f(n) for the largest number of parts when the matchings have size two, we determine f(n) exactly for every order from five to nineteen, narrow order twenty to two consecutive values, and give an explicit asymptotic construction. The engine is a bijection between ordered decompositions and K_4-peelings of the complete graph, each step deleting a perfect matching from four vertices that currently span a clique. This yields the counting bound floor(n(n-4)/4) at once and reduces equality to whether a cubic or near-cubic remainder is reachable. Structural lemmas cut the candidates to connected bridgeless graphs, and a contraction correspondence carries odd orders to the even census one larger, leaving a finite case analysis that we discharge by isomorphism-free reverse search. The bound is attained only at orders five through nine and eleven, and missed by exactly one at every other order we reach. Order eleven is thus an isolated exception rather than a parity phenomenon: the natural equality conjecture fails, and fails irregularly. Upper bounds are certified by fail-closed sweeps over complete cubic censuses, and every decomposition is re-checked against the definition by an independent verifier. Which of its two values order twenty takes remains open.
The degree/diameter problem asks for the largest order of a graph with a given diameter and maximum vertex degree. This has been widely studied and given rise to a recent variation for mixed graphs (graphs with both undirected edges and directed arcs), where an additional bound is placed on the maximum directed out-degree of any vertex. Both problems have applications to network design. Counting the possible number of vertices at each distance from a given vertex gives a bound on the order of a mixed graph satisfying the degree and diameter constraints (the mixed Moore bound). In this paper, we settle an open problem posed by Tuite and Erskine concerning the total regularity of mixed graphs whose order is one less than the mixed Moore bound (almost mixed Moore graphs). We use this result to show that the three known almost mixed Moore graphs of diameter at least three are the only such mixed graphs.