betaFeedback

WorksComputer Science

Subexponential algorithms for structural parameterizations of Vertex Cover in geometric graphs

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 nn-vertex graph, the goal is to decide in time nO(1)2o(k)n^{O(1)}2^{o(k)} if a solution of size at most kk 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\mathcal{C}, the problem takes as input (G,X,k)(G,X,k), where G∖X∈CG \setminus X \in \mathcal{C}, and asks if GG admits a vertex cover of size at most kk. Our goal is to design algorithms for this problem running in time nO(1)2o(∣X∣)n^{O(1)}2^{o(|X|)}. The motivation is that, since ∣X∣|X| is typically arbitrarily smaller than kk, such algorithms might be faster than ETH-tight subexponential algorithms parameterized by kk. We identify two sets of sufficient conditions under which the problem admits a subexponential algorithm: one for the case where C\mathcal{C} is the class of paths, and another for the case where C\mathcal{C} is the class of graphs of constant treedepth. We also provide two applications of these algorithmic results: we prove that ss-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\mathcal{C}. Finally, concerning more restricted graph classes having the ASQGM(ω)ASQGM(ω) property (such as map graphs and HH-minor free graphs), we prove a dichotomy, depending on the maximum treewidth in C\mathcal{C}.

Paper details

vlnc:W_ucswftn9
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC-BY-NC-ND-4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

LLMs

View statement
Looking for related papers…