CS Paper Radar

Subexponential algorithms for structural parameterizations of Vertex Cover in geometric graphs

Marin Bougeret, Juan Pablo Bravo, Daniel Gonçalves

cs.DS ·submitted 2026-11-16 13:28 UTC · v1
theory

Abstract

A number of recent works have investigated the existence of parameterized subexponential algorithms in geometric graph classes for hitting a fixed small graph as a subgraph or as a minor. In this setting, given an $n$-vertex graph, the goal is to decide in time $n^{O(1)}2^{o(k)}$ if a solution of size at most $k$ exists. Inspired by recent results in kernelization for structural parameters, we investigate subexponential algorithms for the Vertex Cover (VC) problem, but parameterized by distance-to-triviality instead of solution size. More formally, given a fixed "trivial" graph class $\mathcal{C}$, the problem takes as input $(G,X,k)$, where $G \setminus X \in \mathcal{C}$, and asks if $G$ admits a vertex cover of size at most $k$. Our goal is to design algorithms for this problem running in time $n^{O(1)}2^{o(|X|)}$. The motivation is that, since $|X|$ is typically arbitrarily smaller than $k$, such algorithms might be faster than ETH-tight subexponential algorithms parameterized by $k$. We identify two sets of sufficient conditions under which the problem admits a subexponential algorithm: one for the case where $\mathcal{C}$ is the class of paths, and another for the case where $\mathcal{C}$ is the class of graphs of constant treedepth. We also provide two applications of these algorithmic results: we prove that $s$-string graphs and pseudo-disk graphs satisfy the first set of conditions, whereas string graphs satisfy the second set. The two sets share a common condition that might be of independent interest, as it implies a property that bounds the treewidth of any string graph in terms of a given modulator to a fixed graph class $\mathcal{C}$. Finally, concerning more restricted graph classes having the $ASQGM(ω)$ property (such as map graphs and $H$-minor free graphs), we prove a dichotomy, depending on the maximum treewidth in $\mathcal{C}$.

Comment
43 pages, 8 figures, submitted

Closest papers

Nearest neighbours by meaning across the whole index.

Minimum Sum Vertex Cover via Minimum Vertex Cover

cs.DS cs.DM ·2026-09-22 ·Ahmad Biniaz, Jean-Lou De Carufel, Anil Maheshwari, Saeed Odak, Michiel Smid
theory similarity 0.74
Abstract

The Minimum Sum Vertex Cover (MSVC) problem asks for an ordering of the vertices of a graph that minimizes the sum, over all edges, of the time at which each edge is first covered. We study the problem through the structure of vertex covers and obtain new approximation and exact algorithms, together with conditional lower bounds. For graphs of maximum degree $Δ$, we show that a simple ordering algorithm based on a minimum vertex cover achieves approximation ratio $R_Δ\le {(\sqrtΔ+1)}/{2}$. For $d$-regular graphs, we give a polynomial-time $1.184$-approximation by combining Max-$k$-Vertex-Cover approximation with a structural bound on optimal prefixes. On the exact side, we give an algorithm parameterized by the vertex cover number $k$ running in $2^{O(k\log k)} + O(n+m)$ time, improving the previous dependence on $k$, where $n$ and $m$ are the number of vertices and edges in the graph, respectively. We also develop a separator-based exact algorithm running in $ 2^{O(\sqrt n \log n)}$ time on planar, bounded-genus, and fixed-minor-free graph classes. Finally, we prove that Minimum Sum Vertex Cover is NP-hard on planar graphs and, assuming ETH, admits no $2^{o(\sqrt n)}$-time exact algorithm on $n$-vertex planar graphs. Thus our planar upper bound is tight up to logarithmic factors in the exponent.

0.20

Vertex Cover Interdiction in Bipartite Graphs

cs.DS ·2026-09-21 ·Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto
similarity 0.71
Abstract · ISAAC 2026

In the vertex cover interdiction problem, we are given an undirected graph $G=(V,E)$, two integers $t$ and $k$ and a vertex subset $B\subseteq V$, and we are asked to find a set $X \subseteq B$ with $|X|\leq t$ such that $X$ hits (i.e., intersects) all the vertex covers of $G$ of size at most $k$. Recently, Grüne and Wulf proved that the problem is $Σ_2^p$-complete. However, their reduction relied on the fact that the vertex cover problem is NP-complete. This, in turn, means that we do not know the complexity status of the vertex cover interdiction problem when the input graph is restricted to a bipartite graph since the vertex cover problem can be solved in polynomial time for bipartite graphs. One of our main results shows that the vertex cover interdiction problem is NP-complete for bipartite graphs. In contrast, when $k$ is restricted to the minimum vertex cover size, i.e., we are only required to hit all the minimum vertex covers, we show that the vertex cover interdiction problem can be solved in polynomial time for bipartite graphs. This motivates us to study the parameterized complexity of the vertex cover interdiction problem for bipartite graphs when the difference of $k$ and the minimum vertex cover size is taken as a parameter. With this parameter, we show that the problem is $\mathrm{W}[1]$-hard, but can be solved in polynomial time when the parameter is constant (i.e., in XP time). We also show that the problem is fixed-parameter tractable when parameterized by $k$.

0.28

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

On (Directed) Width-Parameters of Geometric Spanners

cs.CG ·2026-09-18 ·Kevin Buchin, Carolin Rehs, Torben Scheele
published similarity 0.69
Abstract · Accepted at ISAAC 2026

To speed up algorithms on geometric graphs, it is common to approximate the complete Euclidean graph while maintaining certain geometric properties. A (directed) $t$-spanner $G$ for a point set $P$ in the Euclidean space is a (directed) graph such that for every pair of points, the shortest path in $G$ is at most a factor $t$ longer than the Euclidean distance between those points. In this paper, we investigate $t$-spanners that are bounded by certain graph parameters. Let $κ$ be a graph parameter. We show that for path-width, branch-width and cut-width there is an $\mathcal{O}(n/k^{d/(d-1)})$-spanner $G$ on $P$ with $κ(G)=k$ and that this is asymptotically worst-case optimal. In $\mathbb{R}^2$ we show the same bounds for planar graphs of clique-width or rank-width $k$. In contrast, for tree-depth, we show that there are sets of points for which the dilation cannot be bounded. Therefore, we investigate computing a spanner with tree-depth $k$ and minimum dilation. We show that already for tree-depth $3$ this problem is NP-hard to approximate within any factor strictly less than $\sqrt{2}$, and present an XP-algorithm to compute for a given tree-depth $k$ a graph with dilation at most $2t^*$, where $t^*$ is the minimum dilation. We further extend these results to obtain directed $\mathcal{O}(n/k^{d/(d-1)})$-spanners $G$ with $κ(G)=k$ for $κ$ being directed tree-width, directed path-width or DAG-width and show that also in the directed case, this is asymptotically worst-case optimal.

0.29

Sub-polynomial parameterized complexity of $k$-core

cs.CC ·2026-09-21 ·Yan S. Couto, Cristina G. Fernandes
theory similarity 0.69
Abstract

The $k$-core of a graph is its (unique) largest subgraph with minimum degree at least $k$. For any $k \geq 3$, deciding whether a given vertex belongs to the $k$-core is a P-complete problem, meaning that it is inherently sequential and highly unlikely to admit efficient parallel algorithms, even on graphs of maximum degree $k+1$. This paper investigates alternative parameterizations of the $k$-core problem to identify conditions under which it can be placed into sub-polynomial complexity classes. We prove that the problem is in para-NC$^{2+ε}$ when parameterized by treewidth, and in para-NC$^3$ when parameterized by $k$ on chordal graphs. Furthermore, we introduce a novel NC$^{3}$ algorithm for interval graphs when $k = \mathcal{O}(\lg v(G))$, which relies on an improved parameterization by pathwidth. Finally, we establish corresponding lower bounds, demonstrating that, even with these parameterizations, computing the $k$-core remains L-hard, meaning it requires at least logarithmic space. These findings explore the boundary of parallel tractability for the $k$-core problem by highlighting the graph parameters that make it inherently sequential.

0.23

Exploring Minimal Blocking Sets for Kernelization Lower Bounds for $\mathcal{F}$-Minor Deletion

cs.DS cs.CC ·2026-10-13 ·Ahmed Ghazy, Jakob Greilhuber, Tim A. Hartmann
similarity 0.69
Abstract · Full version of an IPEC 2026 contribution. Abstract has been shortened for arXiv

For Vertex Cover, a minimal blocking set of a graph $G$ is an inclusion-wise minimal vertex set contained in no minimum vertex cover of $G$. Bougeret et al. [SIDMA 2022] showed that, for all minor-closed graph classes $\mathcal{G}$, Vertex Cover has a polynomial kernel parameterized by the distance to $\mathcal{G}$ if and only if $\mathcal{G}$ has bounded minimal blocking sets. In this work, we explore how far this connection between minimal blocking sets and kernelization extends to $\mathcal{F}$-Minor Deletion parameterized by the deletion distance to $\mathcal{G}$. A minimal $\mathcal{F}$-blocking set of $G$ is a minimal vertex set not contained in any optimal $\mathcal{F}$-Minor Deletion solution of $G$. For connected families $\mathcal{F}$, we show that if some graph class $\mathcal{G}$ closed under disjoint union has unbounded minimal $\mathcal{F}$-blocking sets, then $\mathcal{F}$-Minor Deletion parameterized by the deletion distance to $\mathcal{G}$ has no polynomial kernel. This generalizes a result of Hols et al. [SIDMA 2022] for Vertex Cover. We then show that this criterion does not capture all kernelization lower bounds for $\mathcal{F}$-Minor Deletion, even for minor-closed graph classes. Motivated by the work of Dekker and Jansen [Discrete Appl. Math. 2024], we study the more general notion of extended $\mathcal{F}$-blocking sets and the kernelization lower bounds they yield. For every fixed integer $η\geq 1$, Pw-$η$ Deletion is the problem of deleting at most $k$ vertices to reduce the pathwidth to at most $η$. We show that it has no polynomial kernel parameterized by the distance to graphs with pathwidth at most $η+1$. Moreover, for connected families $\mathcal{F}$, we show that $\mathcal{F}$-Minor Deletion parameterized by the distance to graphs with pathwidth at most $\max_{F\in\mathcal{F}} pw(F)+1$ has no polynomial kernel.

0.26

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

Improved Multilayered PCPs and Hypergraph Vertex Cover

cs.CC cs.DS ·2026-09-06 ·Karthik C. S., Dor Minzer
similarity 0.69
Abstract

We present two elementary constructions of multilayered PCPs that improve upon prior constructions in two ways. Specifically, we give one construction of quasi-linear size, and another one with $2$-to-$2$ constraints. Using these constructions we obtain the following results for the hypergraph vertex cover problem: $\bullet$ For $k=3$, for all $\varepsilon>0$, approximating the minimum vertex cover of a given $3$-uniform hypergraph within factor $1+\sqrt{2}-\varepsilon$ is NP-hard. Previously, the best known result due to [Dinur, Guruswami, Khot, Regev, SICOMP 2005] achieved a factor of $2-\varepsilon$. $\bullet$ For $k\geq 4$, for all $\varepsilon>0$, approximating the minimum vertex cover of a given $k$-uniform hypergraph within factor $k-\varepsilon$ is NP-hard, which is tight. Previous works established this result assuming the Unique-Games Conjecture [Khot, Regev, JCSS 2008], and a weaker factor of $k-1-\varepsilon$ for standard NP-hardness [Dinur, Guruswami, Khot, Regev, SICOMP 2005]. $\bullet$ Assuming the Exponential Time Hypothesis, for all $k\geq 3$ and $\varepsilon>0$ there is $C>0$ such that no $2^{n/\log^C n}$-time algorithm approximates the minimum vertex cover in a $k$-uniform, $n$-vertex hypergraph within factor $k-1-\varepsilon$. The proofs were obtained using ChatGPT 5.6 Pro and subsequently rewritten by the communicators.

0.07