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 -vertex graph, the goal is to decide in time if a solution of size at most 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 , the problem takes as input , where , and asks if admits a vertex cover of size at most . Our goal is to design algorithms for this problem running in time . The motivation is that, since is typically arbitrarily smaller than , such algorithms might be faster than ETH-tight subexponential algorithms parameterized by . We identify two sets of sufficient conditions under which the problem admits a subexponential algorithm: one for the case where is the class of paths, and another for the case where is the class of graphs of constant treedepth. We also provide two applications of these algorithmic results: we prove that -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 . Finally, concerning more restricted graph classes having the property (such as map graphs and -minor free graphs), we prove a dichotomy, depending on the maximum treewidth in .