This is the first $O(1)$-approximate algorithm for densest subgraph to break the $\Theta(\sqrt{\lg n})$ round-complexity barrier in the sub-linear MPC model and achieves the following round-approximation tradeoffs.
Abstract
A number of fundamental graph problems admit simple algorithms based on iterative peeling: repeatedly remove all vertices whose current degree is below a fixed threshold. This paradigm underlies algorithms for density-dependent edge orientation, density-dependent coloring, densest subgraph, and $k$-core decomposition. In this paper, we study these problems in the sub-linear MPC model and achieve the following round-approximation tradeoffs. For density-dependent edge orientation, given any integer $t>0$, we compute an orientation with maximum out-degree at most $(2+\epsilon)(t+1)\alpha(G)$ in $O(\lg^{1/(t+2)} n \cdot \operatorname{poly}(\lg \lg n))$ rounds, where $\alpha(G)$ denotes the minimum possible maximum out-degree of an orientation of $G$. In the $\operatorname{poly}(\lg\lg n)$-round regime, this gives an $O(\lg\lg n/\lg\lg\lg n)$-approximation, improving the approximation factor of the recent work by Ghaffari and Grunau [PODC 2025]. We obtain a similar improvement for density-dependent coloring. For densest subgraph, we obtain a $(4+\epsilon)$-approximation in $\widetilde O(\lg^{1/3} n)$ MPC rounds and a $(6+\epsilon)$-approximation in $\widetilde O(\lg^{1/4} n)$ MPC rounds. This improves the $\widetilde O(\sqrt{\lg n})$ round complexity of Ghaffari, Lattanzi, and Mitrovi\'c [ICML 2019] with a slightly larger approximation factor. This is the first $O(1)$-approximate algorithm for densest subgraph to break the $\Theta(\sqrt{\lg n})$ round-complexity barrier in the sub-linear MPC model. For $k$-core decomposition, given any integer $t>0$, we compute approximate coreness values within a factor of $(2+\epsilon)(t+1)$ in $O(\lg^{1/(t+2)} n \cdot \operatorname{poly}(\lg \lg n))$ MPC rounds for any integer $t>0$. This improves the $\widetilde O(\sqrt{\lg n})$ round complexity of Ghaffari, Lattanzi, and Mitrovi\'c [ICML 2019], again giving a round-approximation tradeoff.
The classical Minimum Linear Arrangement (MLA) problem has been studied extensively. It is known to be NP-hard and it admits an $O(\sqrt{\log n}\log\log n)$-approximation [Feige and Lee, IPL, 2007]. MLA can be defined as follows as design problem: Given a graph $G$ with vertex set $V(G)$, design a path $H$ on the same vertex set that minimizes the linear arrangement cost $\sum_{uv\in E(G)}\textrm{dist}_H(u,v)$, where $\textrm{dist}_H(u,v)$ indicates the distance of $u$ and $v$ in $H$. We initiate the study of the generalization in which $H$ is allowed to be a caterpillar graph of maximum degree at most $\Delta$. Caterpillars are the simplest generalization of paths, having pathwidth one and interpolating between paths and stars via the degree parameter $\Delta$. We give an algorithm that lifts any $\alpha$-approximation for MLA to an $(\alpha+3-2/(\Delta-1))$-approximation for our problem, thus obtaining an $O(\sqrt{\log n}\log\log n)$-approximation for our more general problem as well. Moreover, we derive a $4$-approximation whenever MLA is polynomial-time solvable, in particular, for trees. Complementing these results, we prove NP-hardness for every constant $\Delta\geq 2$, and, in stark contrast to MLA, show it remains NP-hard on trees when $\Delta$ is part of the input.
L. Kullmann, Phuoc Trinh, Leon Kellerhals et al.· 0 citations
The notion of linear neighborhood complexity is a very general structural assumption on a graph class, covering most classes of sparse graphs such as planar graphs, graphs excluding a fixed (topological) minor, or bounded expansion graphs, as well as many structured classes of dense graphs, such as graphs of bounded clique-width, twin-width, merge-width, or flip-width. In this work, we present $O(n^2)$-time optimal algorithms for $n$-vertex graphs coming from a class of linear neighborhood complexity for the following problems: $\bullet$ All-Pairs Shortest Paths, $\bullet$ the multiplication of the adjacency matrix $M$ of the input graph with any $n \times n$ matrix. More specifically, after a quadratic preprocessing, we can multiply $M$ with any $n$-vector in $O(n)$ time. This solves several questions raised in [Bonnet, Kim, Geniet, Moon; ICALP'26], and improves and generalizes results in several other recent papers [Bonnet, Giocanti, Ossona de Mendez, Thomass\'e; STACS'23], [Bannach, Marwitz, Tantau; STACS'24], [Anand, van den Brand, McCarty; NeurIPS'26], [Kozma, Opler'26], and [Cardinal, McCarty, Yuditsky'26]. We also extend our results to classes of bounded VC density. In classes of linear neighborhood complexity, we also give a triangle-detection algorithm in randomized linear time $O(n+m)$ in $n$-vertex $m$-edge graphs, a $K_4$-detection algorithm in randomized $O(n \log^5 n + m \log n)$ or deterministic $O(n^2)$ time, and a $K_5$-detection algorithm in randomized $O(n \log^9 n + m \log^5 n)$ time.
Édouard Bonnet, Julien Duron, M. Pilipczuk et al.· 0 citations
Given $A\in\operatorname{GL}(N,2)$ and an integer $K$, we ask whether $A$ can be implemented by at most $K$ CNOT gates on fixed labelled wires with all-to-all connectivity. We prove that this problem is NP-complete. From a finite simple graph $G=(V,E)$, we construct an upper-unitriangular matrix $A_G\in\operatorname{GL}(2|V|+|E|+1,2)$ satisfying $\ell_{\mathrm{CNOT}}(A_G)=2|V|+2|E|+\tau(G)$, where $\tau(G)$ is the minimum vertex-cover size. Each target matrix has $O(N)$ nonzero entries and row Hamming weight at most four. The lower bound unfolds an arbitrary CNOT circuit into an XOR directed acyclic graph and applies projection--contraction operations, allowing cancellation and unrestricted reuse of intermediate parities. For this family, the optimum is unchanged by any finite number of clean or borrowed ancillary wires that must be restored. A polynomial-time decoder further yields NP-hardness of approximation within every fixed additive constant and, through an L-reduction from Minimum Vertex Cover on cubic graphs, APX-hardness of the associated CNOT-circuit optimisation problem.
Antonio Acuaviva, Arturo Acuaviva, Pablo Acuaviva· 0 citations
This paper provides the first truly linear-time approximation scheme for the Densest Subgraph Problem, and uses assignments arising from a flow-based formulation together with a structural carving lemma to progressively carve "sparse" parts of the graph while nearly preserving the densest subgraph.
The main result shows that the exact average-case complexity of this fundamental problem is $\Theta(nk)$ for every $k \leq n^{c'}$ and some $c'\in (0, 1)$, and reveals the average sublinear nature of $k$-colorability: the average-case complexity is linear in $n$, and thus sublinear in the size of the input.
Cassandra Marcussen, Edward Pyne, R. Rubinfeld et al.· 0 citations
A central theme in extremal graph theory is the supersaturation problem, which investigates the minimum number of copies of a target subgraph forced by prescribed edge conditions. This line of research goes back to Rademacher and Erd\H{o}s for triangles, and was later extended to cliques by Lov\'asz and Simonovits in the regime above the Tur\'an threshold. Mubayi further extended this theory to color-critical graphs. Below the Tur\'an threshold, a closely related existence-threshold phenomenon arises in the non-$p$-partite setting: a classical result of Brouwer shows that, for $n\ge 2p+1$, every $n$-vertex non-$p$-partite $K_{p+1}$-free graph has at most $e(T_{n,p})-\lfloor n/p\rfloor+1$ edges. Motivated by this threshold, we investigate a sharp clique-counting problem below the Tur\'an threshold under the non-$p$-partite assumption. Let $p\ge 2$ and $s\ge 1$ be fixed integers. Let $Y_{n,p,s}$ be the graph obtained from $T_{n,p}$ by adding an edge inside a largest part and deleting all but $s$ of the edges from one endpoint of this new edge to a smallest part. Then $e(Y_{n,p,s})=e(T_{n,p})-\lfloor n/p\rfloor+s+1$. We prove that, for all sufficiently large $n$, every $n$-vertex non-$p$-partite graph $G$ with $e(G)\ge e(Y_{n,p,s})$ contains at least as many copies of $K_{p+1}$ as $Y_{n,p,s}$ does. The bound is sharp, as it is attained by the construction $Y_{n,p,s}$. Thus our result provides the exact clique-counting analogue of Brouwer's threshold for non-$p$-partite $K_{p+1}$-free graphs.
