This work presents $O(n^2)$-time optimal algorithms for $n$-vertex graphs coming from a class of linear neighborhood complexity for the following problems: All-Pairs Shortest Paths, and the multiplication of the adjacency matrix of the input graph with any $n \times n$ matrix.
Abstract
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.
The spectral Tur\'an type problem, initiated by Nikiforov in 2007, aims to determine the graphs among $n$-vertex $H$-free graphs having maximum spectral radius. In this paper, we study this problem for $1$-planar graphs, i.e., graphs that admit a drawing in the plane such that each edge is crossed at most once. Recently, Xu and Chang proved that the graphs among all $n$-vertex $K_5$-free $1$-planar graphs having maximum spectral radius lie within a small family of candidates. First, this paper explicitly identifies the unique spectral extremal graph among the $n$-vertex $K_5$-free $1$-planar graphs. Second, it establishes a structural reduction theorem: For any forbidden subgraph $F$ with $\delta(F)\ge2$ that is contained in $K_2\vee P_{n-2}^{2+}$ but not in $K_2\vee I_{n-2}$, every spectral extremal $F$-free $1$-planar graph contains a spanning complete bipartite graph $K_{2,n-2}$, where $P^{2+}_{n-2}$ is obtained from a path $u_1u_2\dots u_{n-2}$ by adding edge $u_1u_{n-2}$ and all edges $u_iu_{i+2}$ for $1\le i\le n-4$, and $I_{n-2}$ denotes the empty graph on $n-2$ vertices. As applications, the graph among all $n$-vertex $C_5$-free (resp. $2C_5$-free) $1$-planar graphs having maximum spectral radius is determined. These results extend spectral Tur\'{a}n type problems for $1$-planar graphs from cliques to cycles and their disjoint union.
The neighbourhood complexity $nc(G,k)$ of a graph $G$ is a quantity measuring, for a graph $G$ and an integer $k$, the maximum possible number (over all vertex subsets $S$ of size $k$) $|\{N[v]\cap S, v\in V(G)\}|$ of $S$-neighbourhoods in $G$. This notion is important in structural graph theory and algorithm design (especially in parameterized complexity, in particular model checking and kernelization). While generally $nc(G,k)\leq 2^k$ and this bound can be achieved, it is known that sparse graphs and structured dense graphs have linear neighbourhood complexity, that is, $nc(G,k)\in O(k)$ for any such graph $G$. However, for many graph classes, the best possible constants are not known. We focus on graphs of bounded treewidth and pathwidth, showing that (when $k\geq w+1$) (i) if $G$ has treewidth $w\geq 2$, then $nc(G,k)\leq (k-w+1)2^{w}+w$, and (ii) if $G$ has pathwidth $w\geq 2$, then $nc(G,k)\leq (k-w+2)2^{w-1}+2k-w-2$. Moreover, we provide constructions that reach these bounds, whenever $w\geq 2$ and $k\geq 2w+1$ ($k\geq 2w-1$ for pathwidth). Interestingly, in contrast, we also have the tight bound $nc(G,k)\leq \frac{7}{3}k$, for graphs $G$ with pathwidth 1 or treewidth 1.
Gaétan Berthe, F. Foucaud, Tuomo Lehtilä et al.· arXiv.org· 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.
This paper asks what structural properties of the graph itself make metric repair tractable, and gives pseudo-polynomial time algorithms for series-parallel graphs, and by generalization, graphs of bounded treewidth and a new algorithm for the length-bounded multicut problem.
Asaf Etgar, A. Gilbert, Jamie Tucker-Foltz· arXiv.org· 0 citations
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.
For a graph $G$, let $h(G)$ be the minimum cardinality of a vertex set meeting every maximum independent set of $G$. We establish two complementary reduction principles for the Bollob\'as--Erd\H{o}s--Tuza conjecture: the conjecture for arbitrary graphs is equivalent to its restriction to regular graphs of any fixed positive linear degree, and, within every hereditary graph class, a uniform sublinear bound is equivalent to a sublinear bound on graphs of every fixed positive linear vertex connectivity. We prove the sharp general estimate \[ h(G)\le \left\lfloor\frac{|V(G)|}{2\alpha(G)+\delta(G)-|V(G)|}\right\rfloor \] whenever the denominator is positive, with equality for balanced complete multipartite graphs. Consequently, every $3$-colorable graph of order $n$ with $\kappa(G)\ge\rho n$ and $\rho>1/3$ has a hitting set of size at most $\lfloor(\rho-1/3)^{-1}\rfloor$; direct use of a $3$-coloring improves this to $6$ when $\kappa(G)>4n/9$ and to the sharp bound $3$ when $\kappa(G)>n/2$. For dense regular graphs with independence ratio greater than $1/4$, we obtain a logarithmic bound, while constructions with linear degree and linear independence number show that $h(G)=\Omega(\sqrt n)$ can still occur. We also prove a logarithmic bound for near-regular $3$-colorable graphs and exhibit a critical family at connectivity $n/3$ that explains the limitations of the degree-surplus and degree-ratio methods.
Hanzhi Bai, Yu-jeong Chang, Jin Yan· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
