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.
Abstract
In the undirected \emph{Densest Subgraph Problem (DSG)} the goal is to output a subset $S$ of vertices of a given graph $G$ that maximizes the quantity $|E(S)|/|S|$, where $E(S)$ is the set of edges in the subgraph induced by $S$. The problem is well studied in both theory and practice, and it admits natural efficient exact algorithms, as well as near-linear time algorithms with a $(1-\varepsilon)$ approximation ratio. However, all previously-known approximation schemes incur logarithmic factors in the size of the graph or other parameters of the graph. This raises the question of whether a linear time $(1-\varepsilon)$-approximation can be obtained for all $\varepsilon>0$. We answer this question affirmatively by providing a $(1-\varepsilon)$-approximation algorithm running in time $O\left(\frac{n+m}{\varepsilon^3}\log \frac{1}{\varepsilon}\right)$, where $m$ and $n$ are respectively the number of edges and vertices of $G$. To the best of our knowledge, this is the first truly linear-time approximation scheme for the problem (when $\varepsilon>0$ is a constant). Our algorithm uses assignments arising from a flow-based formulation together with a structural carving lemma. This lemma allows us to progressively carve"sparse"parts of the graph while nearly preserving the densest subgraph, allowing us to shift heavy computations to smaller instances, which eventually yields the mentioned runtime. Our framework also yields a $(1/2 -\varepsilon)$-approximation for the \emph{Densest At-Least-$k$ Subgraph Problem}, where in addition to maximizing the density, we require the subgraph to have at least $k$ vertices. Our algorithm runs in time $O\left( \frac{(n+m) \log^2 n \log \frac{1}{\varepsilon}}{\varepsilon} \right)$. This nearly matches the known $1/2$ approximation hardness while running in near-linear time.
For a simple graph $G$ of order $n$, let $S_2(G)=\lambda_1(G)+\lambda_2(G)$ denote its spectral sum. We determine, for every $n\geq5$, the exact maximum of $S_2(G)$ and all equality cases. The unique maximizer, up to isomorphism, is the complement of the disjoint union of a suitably balanced complete bipartite graph and isolated vertices, with the sizes of its three parts determined by $n$ modulo $7$. Denoting this graph by $K_n^\star$, we further show that $ S_2(K_n^\star)\leq\frac{8n}{7}-2,$ with equality exactly when $7\mid n$. This proves a conjecture of Kumar, Liu, Monterde, Pragada and Tait, which strengthens the Aouchiche--Hansen 2010 conjecture by extending it from connected graphs to all graphs and by asserting uniqueness of the extremal graph. The result also subsumes the 2008 conjecture of Ebrahimi B., Mohar, Nikiforov, and Ahmady. The proof combines Ky Fan's variational principle with a spectral inequality for weighted Ferrers quotients to reduce the problem to an explicit family whose complements have incidence rank one. Exact integer optimization and a separate equality analysis then yield the maximum and uniqueness.
In the cut-query model, an algorithm is given access to a graph $G = (V, E)$ \emph{only} via cut queries. This model has seen significant attention in the undirected graph setting, with works establishing $O(n)$ cut query algorithms for computing the global minimum cut, $\widetilde{O}(n^{3/2})$ cut query algorithms for all pairs minimum cut, and many more. However, despite this vast array of progress in designing sub-quadratic query algorithms for computing properties of undirected graphs, there has been \emph{no} progress in designing such algorithms in directed graphs. Indeed, even for basic problems like whether a vertex $t$ is reachable from a vertex $s$, the cut query complexity is only known to be bounded in the interval $[\Omega(n), O(n^2 / \log n)]$. In this work, we begin a systematic study of these basic problems in directed \emph{acyclic} graphs (DAGs). In this setting, we show that reachability from a single vertex and even topological sorting are both computable in $O(n \log^3 n)$ many cut queries. As a consequence, we also obtain an algorithm which, for any \emph{arbitrary} directed graph $G$, uses only $O(n \log^3 n)$ cut queries and determines whether $G$ contains a cycle.
Given graphs $H$ and $F$, the generalized Tur\'{a}n number ${\rm ex}(n,H,F)$ is the maximum number of copies of $H$ in an $n$-vertex $F$-free graph. Alon and Shikhelman (J. Combin. Theory Ser. B, 2016) initiated the systematic study of generalized Tur\'{a}n problems. Let $T$ be a tree on $k$ vertices, and write $n=a(k-1)+b$, where $0\leq b<k-1$. Recently, Gerbner and Palmer (Electron. J. Combin., 2026) proposed the following conjecture: for every $r\geq3$, the graph $aK_{k-1}\cup K_b$ maximizes the number of copies of $K_r$ among all $n$-vertex $T$-free graphs. In this paper, we verify their conjecture when $r=k-2$ or $r=k-3\geq5$. More precisely, we show that ${\rm ex}(n,K_r,T)=a\binom{k-1}{r}+\binom{b}{r}$ and characterize all extremal graphs.
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
For every $\varepsilon>0$, it is NP-hard to $n^{1-\varepsilon}$-approximate Max Independent Set in $n$-vertex graphs [Hastad'96, Zuckerman'07]. In triangle-free graphs, a simple argument gives a polynomial-time $n^{1/2}$-approximation algorithm, whereas, for every $\varepsilon>0$, an $n^{1/4-\varepsilon}$-approximation algorithm would imply that NP $\subseteq$ BPP [Bonnet, Thomass\'e, Tran, Watrigant; ESA'20]. In this note, we close this gap by proving the corresponding hardness against $n^{1/2-\varepsilon}$-approximation algorithms. The reduction is very simple and uses the Moser-Tardos resampling algorithm to make the constructed graphs triangle-free. The soundness uses a result of Haeupler, Saha, and Srinivasan building on the proof of Moser and Tardos, to upper-bound the probability that a fixed relatively large subset is an independent set after the Moser-Tardos algorithm terminates. We generalize this scheme and show that, for any nonempty finite family $\mathcal F$ of graphs, each containing at least one cycle, for any $\varepsilon>0$, an $n^{\mu(\mathcal F)-\varepsilon}$-approximation algorithm for Max Independent Set in graphs excluding every member of $\mathcal F$ as a subgraph implies that NP $\subseteq$ BPP, where $\mu(\mathcal F) := 1 - \max\limits_{H \in \mathcal F}~\min\limits_{U \subseteq V(H), H[U] \text{contains a cycle}} (|U|-2)/(|E(H[U])|-1)$.
In this paper, we consider an easy greedy approximation algorithm, the good-bad algorithm, introduced by Cou\"etoux for finding a minimum-cost set of edges such that every connected component has at least $k$ vertices. Cou\"etoux proves that the good-bad algorithm achieves a $3/2$-approximation for this problem. Davis and Williamson extend this result to the more general problem of finding a minimum-cost edge set that contains at least one edge from every cut $S\subseteq V$ satisfying $h(S) = 1$ where $h:2^V \rightarrow \{0,1\}$ is downward monotone; that is, $h(S) = 1$ implies $h(T) = 1$ for every nonempty subset $T \subseteq S$. The original problem corresponds to $h(S) =1$ when $|S|<k$. We give a simplified analysis of the good-bad algorithm for downward monotone functions.
Shayan Ranjbarzadeh, David P. Williamson, Hannane Yaghoubizade· 0 citations