CS Paper Radar

Running-Time Lower Bounds under FPT $\neq$ W[1]

Hendrik Molter

cs.DS cs.CC ·submitted 2026-11-19 13:22 UTC · v1

Abstract

We revisit running-time lower bounds historically based on the Exponential Time Hypothesis. Our case study asks how much of their quantitative content can be recovered under the assumption FPT $\neq$ W[1]. The reductions encode the choice of a clique in few bits and control the target parameter in terms of that encoding. This makes a sufficiently fast algorithm for the target problem yield a fixed-parameter algorithm for deciding whether a graph has a clique of the requested size. We obtain twelve lower bounds for deterministic algorithms across graph, string, and integer feasibility problems, including bounds that hold under structural restrictions. In several cases the same function of the parameter appears in the exponent as in the historical bound, with the additional requirement that the cutoff for any prescribed saving in the exponent be computable.

Closest papers

Nearest neighbours by meaning across the whole index.

Deterministic Streaming Lower Bounds for Approximate Maximum Clique and Maximum Independent Set

cs.DS ·2026-09-16 ·Adithya Diddapur
theory similarity 0.69
Abstract · 25 pages, 1 figure

We study the canonical \textsf{Maximum Clique} and \textsf{Maximum Independent Set} problems in the one-pass edge-arrival graph streaming setting. Here, the edges of some input graph $G = (V,E)$ are presented one at a time (possibly including deletions), before an algorithm needs to produce either a large clique or independent set at the end of the stream, with the focus being on space complexity. We are interested in finding $β$-approximate solutions, for any $β\geq 1$. Previous work gave an algorithm using $\tilde{O}\left(n^2/β^2\right)$ bits of space, together with a corresponding $\tildeΩ\left(n^2/β^2\right)$ two-party communication lower bound [Halldórsson et al., ICALP'12], seeming to resolve the problem. However, their algorithm crucially relies on randomness, and the best known deterministic algorithm remains a folklore derandomisation using $O\left(n^2/β\right)$ bits of space, leaving a (deterministic) gap of size $\tilde{O}(β)$. We make progress towards this gap with a strong lower bound for a restricted range of $β$: whenever $β\leq \sqrt{n}/36\log n$, any deterministic algorithm for either problem must use $Ω\left(\frac{n^2}{β\cdot\log n}\right)$ bits of space. Our proof is via a two-party one-way communication lower bound, and highlights the power of randomness when approaching either of these problems.

0.30

Enumerating Small Potential Maximal Cliques with Fixed-Parameter Delay

cs.DS cs.DB ·2026-10-17 ·Batya Kenig
similarity 0.67
Abstract

A potential maximal clique (PMC) of a graph $G$ is a nonempty vertex set that forms a maximal clique in some minimal triangulation of $G$. Listing the PMCs of a graph is a key step in exact algorithms for computing treewidth, minimum fill-in, and related graph parameters. We present a deterministic algorithm that enumerates all PMCs of cardinality at most $k$ in an $n$-vertex graph $G$, without repetition, with delay $2^{O(k^3)}n^4\log n$. This bound also covers the preprocessing time before the first output, the time from the last output to termination, and the total running time when no such PMC exists. At the core of our enumeration algorithm is a procedure that solves the following constrained search problem within the same time bound: given sets of required and excluded vertices $I,O\subseteq V(G)$, find a PMC $Ω$ of size at most $k$ satisfying $I\subseteqΩ$ and $Ω\cap O=\emptyset$, or determine that none exists. Our enumeration algorithm directly supports these inclusion and exclusion constraints as well. Our approach builds on the \emph{recursive understanding} technique of Chitnis et al.~\cite{chitnis2016} and the reduction to unbreakable graphs of Lokshtanov et al.~\cite{lokshtanov2018}. A graph is $(q,k)$-unbreakable if no removal of at most $k$ vertices leaves two disjoint unions of connected components that each contain more than $q$ vertices. We first solve constrained PMC search on $(q,k)$-unbreakable graphs, and then apply this procedure to replace separated subgraphs with graphs of size $2^{O(k^2)}$ that preserve the existence of a constrained solution for every graph attached along the shared boundary.

0.21

Lower Bounds for Domination-Type Problems Parameterized by Rank-Width

cs.CC ·2026-08-19 ·Chenghua Liu, Boning Meng
theory similarity 0.66
Abstract

For graphs of rank-width \(w\), the algorithms of Bui-Xuan, Telle, and Vatshelle (\emph{Theor. Comput. Sci.}, 2013) for fixed finite/cofinite \((σ,ρ)\)-problems and of Bergougnoux and Kanté (\emph{SIAM J. Discrete Math.}, 2021) for Connected Dominating Set run in \(2^{O(w^2)}n^{O(1)}\) time. Bergougnoux, Korhonen, and Nederlof (STACS 2023) proved a matching lower bound under the Exponential Time Hypothesis (ETH) for \emph{Weighted} Dominating Set, but left the unweighted problem open. We prove that, unless ETH fails, Dominating Set admits no \(2^{o(w^2)}n^{O(1)}\)-time algorithm, even on split graphs and, separately, on bipartite graphs of diameter at most four, and even with a rank-decomposition or witnessing vertex order supplied. The proof replaces the earlier weights by a two-guard gadget and uses a low-rank equality gadget to carry \(k^2\) assignment bits through cuts of rank \(O(k)\). The construction also gives the same lower bound for Independent, Connected, and Total Dominating Set on restricted graph classes and applies to a broad family of \((σ,ρ)\)-set problems. This family includes cases in which \(σ\) is neither finite nor cofinite and contains the entire nontrivial cofinite--cofinite minimization regime. Every solution within the target budget has target size and corresponds bijectively to a satisfying assignment. Under the counting Exponential Time Hypothesis (\(\#\mathrm{ETH}\)), the same bounds therefore hold for counting solutions of size at most or exactly the target. Together with the known algorithms, our results show that the quadratic dependence on the rank-width \(w\) is optimal up to constant factors in the exponent for the classical problems above and throughout the covered finite/cofinite regime.

0.18

Hitting Minors: Stronger Lower Bounds

cs.DS cs.CC ·2026-10-13 ·Jongseo Lee, Roohani Sharma, Sebastian Wiederrecht
theory similarity 0.65
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

Unconditional Boolean Dynamic Lower Bounds from Disjointness

cs.DS cs.CC ·2026-10-07 ·Young Kun Ko
theory similarity 0.65
Abstract · 48 pages, 3 figures. v2: main result stated for the multiphase problem; appendix extended to further dynamic problems; introduction revised.…

We prove an unconditional $Ω((\log n/\log\log n)^2)$ lower bound on the maximum of the worst-case update time and expected query time for the insert-only version of Patrascu's multiphase Disjointness problem [STOC 2010]. The bound holds in the zero-error cell-probe model with logarithmic word size. Patrascu's reductions transfer it to directed reachability under edge insertions, already on directed acyclic graphs of depth $2$. This improves the $\widetildeΩ(\log^{3/2} n)$ bound of Larsen and Yu [SICOMP 2025] to the quadratic-logarithmic scale previously attained for dynamic range counting and multiphase Inner Product. The bound also transfers to a broad collection of dynamic graph, algebraic, geometric, and string problems. We also obtain a separation between amortized and worst-case time for streaming regular-expression membership. For a simple family of expressions of maximum length $M$ over a polynomial-size alphabet, a deterministic algorithm uses $O(1)$ amortized time per symbol on every input stream, whereas every zero-error cell-probe algorithm with word size $w=Θ(\log M)$ requires $Ω((\log M/\log\log M)^2)$ time on some symbol. The proof adapts Ko's 2.5-round multiphase communication framework [FOCS 2026] from Inner Product to Disjointness. Our main technical observation is that the protocol's verification step allows a one-sided corruption bound to replace the discrepancy property used for Inner Product.

0.24

Forbidden Subgraphs of Graphs with Low Bandwidth

cs.DS ·2026-09-01 ·Maria Chudnovsky, Daniel Lokshtanov, Eran Nevo
top venuetheory similarity 0.65
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

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.64
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

Reachability Diameter: Beyond the Square-Root Barrier, with Polynomial Hardness

cs.DS ·2026-11-03 ·Hector Tierno, Shuang Yang
theory similarity 0.64
Abstract

The reachability diameter of a directed graph is the maximum finite shortest-path distance across all pairs of vertices. It has received recent attention under this name, although the underlying quantity has long played a central role in shortcut set and parallel reachability. Notably, Bals et al. establish hardness for every polynomial-factor approximation in nearly-linear time for weighted digraphs. Yet they give $n^{1/2+o(1)}$-approximation in the unweighted regime with nearly-linear running time, and their conditional lower bounds rule out certain constants only, leaving open whether polynomial loss is necessary. We give a randomized algorithm that estimates the reachability diameter of an unweighted digraph within a factor $n^{1/3+o(1)}$, with high probability, in $\widetilde{O}(m+n)$ time. We complement our algorithm with a lower bound conditional on the 3-uniform Hyperclique hypothesis, ruling out an $n^{2/15-\varepsilon}$-approximation in $\widetilde{O}(m+n)$ time for every fixed $\varepsilon\in(0,2/15)$, establishing the necessity of polynomial loss for nearly-linear time algorithms.

0.25