Algorithms and Turing Kernels for Detecting and Counting Small Patterns in Unit Disk Graphs

Abstract

In this paper we investigate the parameterized complexity of the task of counting and detecting occurrences of small patterns in unit disk graphs: Given an n-vertex unit disk graph G with an embedding of ply p (that is, the graph is represented as intersection graph with closed disks of unit size, and each point is contained in at most p disks) and a k-vertex unit disk graph P, count the number of (induced) copies of P in G. For general patterns P, we give an O(pk/logk)nO(1) time algorithm for counting pattern occurrences. We show this is tight, even for ply p=2 and k=n: any 2o(n/logn)nO(1) time algorithm violates the Exponential Time Hypothesis (ETH). For most natural classes of patterns, such as connected graphs and independent sets we present the following results: First, we give an (pk)O(pk)nO(1) time algorithm, which is nearly tight under the ETH for bounded ply and many patterns. Second, for p=kO(1) we provide a Turing kernelization (i.e. we give a polynomial time preprocessing algorithm to reduce the instance size to kO(1)). Our approach combines previous tools developed for planar subgraph isomorphism such as ‘efficient inclusion-exclusion’ from [Nederlof STOC’20], and ‘isomorphisms checks’ from [Bodlaender et al. ICALP’16] with a different separator hierarchy and a new bound on the number of non-isomorphic separations of small order tailored for unit disk graphs.