Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering
| Autor: | Daniel Lokshtanov, Michał Pilipczuk, Saket Saurabh, Fedor V. Fomin, Marcin Pilipczuk, Dániel Marx |
|---|---|
| Rok vydání: | 2022 |
| Předmět: |
FOS: Computer and information sciences
General Computer Science Apex graph General Mathematics Subgraph isomorphism problem Vertex cover Parameterized complexity 0102 computer and information sciences 02 engineering and technology 01 natural sciences Bidimensionality Vertex (geometry) Planar graph Combinatorics Treewidth symbols.namesake 010201 computation theory & mathematics Computer Science - Data Structures and Algorithms 0202 electrical engineering electronic engineering information engineering symbols Data Structures and Algorithms (cs.DS) 020201 artificial intelligence & image processing Mathematics |
| Zdroj: | FOCS |
| ISSN: | 1095-7111 0097-5397 |
| Popis: | We prove the following theorem. Given a planar graph $G$ and an integer $k$, it is possible in polynomial time to randomly sample a subset $A$ of vertices of $G$ with the following properties: (i) $A$ induces a subgraph of $G$ of treewidth $\mathcal{O}(\sqrt{k}\log k)$, and (ii) for every connected subgraph $H$ of $G$ on at most $k$ vertices, the probability that $A$ covers the whole vertex set of $H$ is at least $(2^{\mathcal{O}(\sqrt{k}\log^2 k)}\cdot n^{\mathcal{O}(1)})^{-1}$, where $n$ is the number of vertices of $G$. Together with standard dynamic programming techniques for graphs of bounded treewidth, this result gives a versatile technique for obtaining (randomized) subexponential parameterized algorithms for problems on planar graphs, usually with running time bound $2^{\mathcal{O}(\sqrt{k} \log^2 k)} n^{\mathcal{O}(1)}$. The technique can be applied to problems expressible as searching for a small, connected pattern with a prescribed property in a large host graph, examples of such problems include Directed $k$-Path, Weighted $k$-Path, Vertex Cover Local Search, and Subgraph Isomorphism, among others. Up to this point, it was open whether these problems can be solved in subexponential parameterized time on planar graphs, because they are not amenable to the classic technique of bidimensionality. Furthermore, all our results hold in fact on any class of graphs that exclude a fixed apex graph as a minor, in particular on graphs embeddable in any fixed surface. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|