Subexponential algorithms for structural parameterizations of Vertex Cover in geometric graphs

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}$.

Authors

Publication Details

Journal
arXiv (Cornell University)
Published
2026-11-16
DOI
https://doi.org/10.48550/arxiv.2611.21078
Primary Topic
Advanced Graph Theory Research
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Subexponential algorithms for structural parameterizations of Vertex Cover in geometric graphs

Daniel Gonçalves, Marin Bougeret, JUAN PABLO BRAVO
arXiv (Cornell University)
Advanced Graph Theory Research
preprint

Subexponential algorithms for structural parameterizations of Vertex Cover in geometric graphs

Daniel Gonçalves, Marin Bougeret, JUAN PABLO BRAVO
preprint en

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}$.

arXiv (Cornell University)
Advanced Graph Theory Research
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon