Detecting and counting small patterns in planar graphs in subexponential parameterized time

Abstract

We resolve the fine-grained parameterized complexity of detecting and counting small patterns in planar graphs, assuming the Exponential Time Hypothesis. Given an n-vertex planar graph G and a k-vertex pattern graph P, we compute the number of (induced) copies of P in G in time 2Õ(√k) n O(1), if P is a matching, independent set, or connected bounded maximum degree graph, 2 O(k/logk) n O(1), for any pattern P. Our results significantly advance the state of the art of the planar graph isomorphism problem: No 2 o(k) n O(1) time algorithms where previously known for counting patterns even in very restricted cases such as independent sets in subgraphs of grids, Even for detection, no 2 O(k/logk) n O(1) time algorithms for unrestricted patterns P were previously known, Our run times cannot be improved assuming the Exponential Time Hypothesis (ETH). Our results are a corollary of the following general result: We compute the number of (induced) copies of P in G in 2Õ(√k)(σ(P)n) O(1) time, where σ(P) denotes the number of non-isomorphic separations of P of order Õ(√k). To obtain the first sub-exponential time algorithms, we introduce a new general technique that we call efficient inclusion-exclusion. This technique allows us to efficiently use hierarchies of separators for counting problems. To resolve the optimal complexity of planar subgraph isomorphism we provide another technique that we call balanced cycle sparsification. This technique allows us to obtain from one balanced cycle separator in a planar graphs a family of balanced cycle separators that have limited mutual overlap, implying one separator has few vertices of the pattern copy.