CS Paper Radar

NP-hardness of additive approximation for generalized Turán problems

Yihan Chen, Jialin He, Xihe Li, Jie Ma, Tianying Xie

cs.CC math.CO ·submitted 2026-10-12 08:13 UTC · v2

Abstract

Given a graph $T$ and a nonempty family $\mathcal{F}$ of graphs, let $\operatorname{ex}(G, T, \mathcal{F})$ denote the maximum number of copies of $T$ in an $\mathcal{F}$-free subgraph of a host graph $G$. Alon and Shikhelman [Algorithmica, 2022] conjectured that if $e(T)> 0$ and no member of $\mathcal{F}$ is a subgraph of a blow-up of $T$, then for every $\varepsilon>0$, approximating $\operatorname{ex}(G, T, \mathcal{F})$ within an additive error of $n^{v(T)-\varepsilon}$ is NP-hard for an input graph $G$ on $n$ vertices. Previous advances toward this conjecture include the resolution of the canonical case $T=K_2$ by Alon, Shapira, and Sudakov [Ann. of Math., 2009], as well as the case of $\operatorname{ex}(G,K_m,K_k)$ by Alon and Shikhelman. In this paper, we confirm this conjecture for every bipartite graph $T$ and every clique $T$. Our proof reductions combine several techniques, including iterative leaf additions, symmetric rooted extensions, and random transversals. Together, they encode the optimal value of the NP-hard Max $r$-Colorable Subgraph problem into the objectives $\operatorname{ex}(G, T, \mathcal{F})$ for a suitably constructed graph $G$.

Comment
34 pages, 0 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Hitting Minors: Stronger Lower Bounds

cs.DS cs.CC ·2026-10-13 ·Jongseo Lee, Roohani Sharma, Sebastian Wiederrecht
theory similarity 0.69
Abstract · 24 pages, 12 figures

For a fixed finite collection of graphs $\mathcal{F}$, the $\mathcal{F}$-Minor-Free Deletion problem asks, given a graph $G$ and an integer $k$, whether there is a set $S\subseteq V(G)$ with $|S|\leq k$ such that $G-S$ contains no graph of $\mathcal{F}$ as a minor. This generalizes Vertex Cover, Feedback Vertex Set, and Vertex Planarization, among many others. Baste, Sau, and Thilikos [JCSS 2020, SICOMP 2023] showed that, assuming the Exponential Time Hypothesis (ETH), there are collections $\mathcal{F}$ for which the problem cannot be solved in time $2^{o(\mathrm{tw}\log\mathrm{tw})}n^{O(1)}$ on $n$-vertex graphs of treewidth $\mathrm{tw}$, and gave a matching algorithm. We ask whether this super-exponential dependence persists under more restrictive structural parameters. First, we strengthen their lower bound. Assuming ETH, for every fixed $h\geq 6$, $\{P_h\}$-Minor-Free Deletion, where $P_h$ is the path on $h$ vertices, cannot be solved in time $2^{o(t\log t)}n^{O(1)}$, where $t=\mathrm{fvs}+\mathrm{td}$ is the sum of the feedback vertex set number and treedepth of the input graph. These two parameters are incomparable, but both individually upper bound the treewidth. Together with the $2^{O(\mathrm{tw}\log\mathrm{tw})}n^{O(1)}$-time algorithm of Baste, Sau, and Thilikos [SICOMP 2023], our lower bound is tight. In contrast, we show that asymptotically faster algorithms are possible when parameterized by the vertex cover number $\mathrm{vc}$. Specifically, for any finite family $\mathcal{F}$, $\mathcal{F}$-Minor-Free Deletion can be solved in time $2^{O(\mathrm{vc})}n^{O(1)}$. Taken together, our results show that the boundary between single-exponential and super-exponential complexity for this problem lies between the vertex cover number and the feedback vertex set number (plus treedepth).

0.22

Forbidden Subgraphs of Graphs with Low Bandwidth

cs.DS ·2026-09-01 ·Maria Chudnovsky, Daniel Lokshtanov, Eran Nevo
top venuetheory similarity 0.67
Abstract

A layout of a graph G is an injective function $f : V(G) \rightarrow Z$, and the bandwidth of a layout f is $bw(G,f) = max_{uv \in E(G)} |f(u) - f(v)|$. The bandwidth bw(G) of G is the minimum bandwidth of a layout of G. Computing the bandwidth of a graph is a notoriously hard problem: assuming P != NP, there is no polynomial time algorithm, even on very restricted classes of trees [Monien, SIAM Journal on Algebraic Discrete Methods, 1986], and no constant factor approximation, even on trees [Dubey et al., JCSS 2011]. Assuming the Exponential Time Hypothesis, there is no algorithm with running time $f(k)n^{o(k)}$ to determine whether an input graph has bandwidth at most k, even on very restricted classes of trees [Dregi and Lokshtanov, ICALP 2014]. In this paper we show that {\sc Bandwidth} on general graphs is FPT-approximable. In particular we give an algorithm that takes as input a graph G and an integer k, runs in time $2^{O(9^k)}n^{O(1)}$, and outputs a subtree T of G such that $bw(T) \geq k$ or a layout of G of bandwidth at most $(10^{85} k^{28})^{4^k}$. This resolves in the affirmative an open problem of Chung and Seymour [Discrete Mathematics, 1989], who asked whether the bandwidth of every graph G is upper bounded in terms of the maximum bandwidth of a subtree of G. Our theorem leads to a forbidden subgraph characterization for graphs of bounded bandwidth, and can be seen as an analog for bandwidth of the classic grid minor theorem for treewidth, the forbidden subtree theorem for pathwidth, and the forbidden subpath theorem for treedepth.

0.55

Max Independent Set Remains NP-hard when Excluding a Planar Induced Minor (and More)

cs.CC cs.DMcs.DSmath.CO ·2026-09-10 ·Édouard Bonnet, Yeonsu Chang
similarity 0.64
Abstract · 34 pages, 11 figures

We show that Max Independent Set (MIS) remains NP-hard in graphs excluding the $5 \times 5$ grid as an induced minor. This negatively answers a question of Dallard--Milanič--Štorgel that has attracted sustained attention, and refutes a conjecture by Gartland and Lokshtanov. Unless $N$-variable 3-SAT can be solved in time $2^{\mathcal O(N^{1-\varepsilon})}$ for some $\varepsilon > 0$, MIS requires $2^{Ω(n^{1/2-o(1)})}$ time on $n$-vertex graphs in this class. This complements a $2^{\widetilde{O}(n^{2/3})}$-time algorithm on any $H$-induced-minor-free class by Korhonen and Lokshtanov. Exploiting a connection between low twin-width or reduced parameters on one hand and planar-induced-minor-freeness on the other, we further show that 3-Coloring, Feedback Vertex Set and Dominating Set are NP-complete on weakly sparse graphs of reduced component max-leaf (hence twin-width) at most 3, even when a witnessing contraction sequence is given. Classes of bounded reduced component max-leaf (by any constant) and of twin-width at most 3 are known to exclude a fixed planar graph as an induced minor. The 3-Coloring and Feedback Vertex Set results refute more cases of the Gartland--Lokshtanov conjecture, even when the inputs are weakly sparse. The complexity of MIS in weakly sparse graphs excluding a planar induced minor remains open.

0.48

A Linear-Time Approximation Scheme for the Densest Subgraph Problem

cs.DS ·2026-08-11 ·Elena Grigorescu, Mehrshad Taziki
similarity 0.63
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.

0.04

Polynomial Lower Bounds for Steiner Shortcuts via Test Functions

cs.DS ·2026-11-04 ·Aaron Bernstein, Henry Fleischmann, Bernhard Haeupler, Gary Hoppenworth, Thatchaphol Saranurak
theory similarity 0.63
Abstract · 33 + 3 pages

The Steiner shortcut problem asks whether every directed graph $G=(V,E)$ with $n$ vertices and $m$ edges admits an augmentation $G_{+}=(V\cup V_{+},E\cup E_{+})$ with $m^{1+o(1)}$ edges such that $G_+$ has the same reachability structure as $G$ (i.e. for all $s,t\in V$, $s$ reaches $t$ in $G$ iff $s$ reaches $t$ in $G_+$), and the diameter of $G_{+}$ is $m^{o(1)}$. This is a core combinatorial question underlying many reachability algorithms in the dynamic, streaming, and CONGEST models, and all parallel algorithms with almost-linear work and sublinear depth. A sequence of works ruled out such a shortcut $G_{+}$ in the non-Steiner setting where $V_{+}=\emptyset$. However, as recently shown by Bernstein et al. [STOC '26], all known non-Steiner lower-bound constructions fail once Steiner vertices $V_{+}$ are allowed. This paper rules out almost-optimal Steiner shortcuts: we show an infinite family of graphs $G=(V,E)$ with the property that, for any $\varepsilon>0$, a Steiner shortcut $G_{+}=(V\cup V_{+},E\cup E_{+})$ with $m^{1+\varepsilon}$ edges must have diameter at least $n^{1/56-O(\varepsilon)}$. Our construction strengthens the standard non-Steiner lower-bound framework via an additional structure that allows Steiner vertices to be replaced by original vertices; we can then reduce back to the standard arguments without Steiner vertices. This new structure is achieved via a new general strategy based on test functions, which is quite flexible and can potentially be extended to applications beyond our work. We also generalize our lower bound to exact Steiner hopsets in undirected graphs and to depth reduction for monotone circuits. The latter significantly strengthens the classical lower bound based on Sylvester matrices.

0.27

An Improved Upper Bound for the Turán Number of the Hexagon

cs.DM math.CO ·2026-09-09 ·Sandip Das, Sk Samim Islam, Aashirwad Mohapatra, Saumya Sen
theory similarity 0.63
Abstract · 9 pages

For a graph $F$, the Turán number $\operatorname{ex}(n,F)$ is the maximum number of edges in an $n$-vertex graph containing no copy of $F$. Determining the Turán numbers of even cycles is a central problem in extremal graph theory and remains open in general. For $C_6$, the best previous upper bound was due to Füredi, Naor, and Verstraëte [Advances in Mathematics, 2006], who proved that, for sufficiently large positive integer $n$, $$ \operatorname{ex}(n,C_6) \leq λn^{4/3}+O(n)<0.6272 n^{4/3}, $$ where $λ$ is the real root of $ 16λ^3-4λ^2+λ-3=0$. We improve this bound by showing that, for sufficiently large positive integer $n$, $$ \operatorname{ex}(n,C_6) \leq αn^{4/3}+O(n)<0.6144 n^{4/3}, $$ where $α$ is the unique real root of $ 4 α^{3} (3/2)^{1-1/(2α)} =1$ in the interval $(1/2,2/3)$.

0.27

Vertex Deletion on $H$-Induced-Minor-Free Graphs: Subexponential FPT Algorithms and Approximation Schemes

cs.DS cs.DM ·2026-11-06 ·Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, Meirav Zehavi
similarity 0.62
Abstract

We study vertex-deletion problems on string graphs and, more generally, on graphs excluding a fixed graph as an induced minor. For every fixed graph $H$, fixed nonnegative integer $t$, and fixed monadic second-order formula $φ$, we consider the problem of finding a minimum-cardinality set $S$ such that $G-S$ has treewidth at most $t$ and satisfies $φ$. This captures classic problems such as Vertex Cover, Feedback Vertex Set, and deletion to graphs of any fixed bounded treewidth. We give an algorithm with running time $2^{k^{2/3} \log^{O(1)} k}n^{O(1)}$ on $H$-induced-minor-free graphs, where $k$ is the optimum deletion-set size. This resolves in the affirmative the open problem highlighted by Bonnet and Rzążewski [Algorithmica 2019] and Berthe, Bougeret, Gonçalves, and Raymond [ICALP 2025] regarding the existence of a subexponential parameterized algorithm for Feedback Vertex Set on string graphs. Our algorithm significantly improves over existing parameterized algorithms for more restricted classes of problems on more restricted classes of graphs. When the property defined by $φ$ is hereditary, we also obtain a quasi-polynomial time approximation scheme, namely an algorithm that produces a $(1+\varepsilon)$-approximate solution in quasi-polynomial time. Both the sub-exponential algorithm and the quasi-polynomial time approximation scheme build on the same new structural and algorithmic insights.

0.20

Sharp Bounds for Graph-Codes Avoiding Complete Bipartite Differences

cs.IT math.CO ·2026-10-26 ·Nader H. Bshouty
theory similarity 0.61
Abstract

Let $d_{K_{s,t}}(n)$ be the largest fraction of all graphs on $[n]$ in a family containing no two distinct members whose symmetric difference is a copy of $K_{s,t}$. We determine this maximum density for every fixed pair of positive integers $s,t$. If both part sizes are odd, it is known that the density is exactly $1/2$. Otherwise, let $2h$ be the largest even part size. We prove $$ d_{K_{s,t}}(n)=Θ_{s,t}(n^{-h}). $$ For $h>1$, this improves the general $O_{s,t}(1/n)$ upper bound obtained from Alon's two-copy gluing theorem~\cite{Alon2024}. The sharp bounds for even stars were already proved by Alon and are recovered as special cases. The upper bound uses the Frankl--Füredi forbidden-intersection theorem. For the lower bound, we construct binary linear codes using BCH codes. When exactly one part size is even, we assign to each edge the sum of the binary vectors assigned to its endpoints. When both part sizes are even, we identify these vectors with elements of a finite field and assign to each edge the product of its endpoint elements. In both cases, every copy of $K_{s,t}$ has a nonzero syndrome.

0.27