Answers are grounded in this paper and cite their sources.
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 nO(1)2ᵒ⁽ᵏ⁾ 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 C, the problem takes as input $(G,X,k)$, where G X ∈ 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 nO(1)2o(|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 C is the class of paths, and another for the case where 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 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 C.
No takes yet. Share an insight, caveat, or question.
Bougeret et al. (2026) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: