| Title: |
Algorithms and Turing Kernels for Detecting and Counting Small Patterns in Unit Disk Graphs |
| Authors: |
Nederlof, Jesper; Szilágyi, Krisztina; Sub Algorithms and Complexity; Algorithms and Complexity; Fernau, Henning; Gaspers, Serge; Klasing, Ralf |
| Publication Year: |
2024 |
| Subject Terms: |
Parameterized complexity; Subgraph isomorphism; Unit disk graphs; Taverne |
| Description: |
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. |
| Document Type: |
book part |
| File Description: |
application/pdf |
| Language: |
English |
| ISSN: |
0302-9743 |
| Relation: |
https://dspace.library.uu.nl/handle/1874/482129 |
| Availability: |
https://dspace.library.uu.nl/handle/1874/482129 |
| Rights: |
info:eu-repo/semantics/OpenAccess |
| Accession Number: |
edsbas.E9185F39 |
| Database: |
BASE |