| 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 |
| Publication Year: |
2025 |
| Subject Terms: |
Parameterized complexity; Subgraph isomorphism; Unit disk graphs; Theoretical Computer Science; General Computer Science; Computer Networks and Communications; Computational Theory and Mathematics; Applied Mathematics |
| Description: |
In this paper we investigate the parameterized complexity of counting and detecting small patterns in unit disk graphs: Given an n-vertex unit disk graph G with an embedding of ply p (i.e. G is an intersection graph of closed unit disks, 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 2O(pk/logk)nO(1) time algorithm for counting pattern occurrences. We show this is tight, even for ply p=2: any 2o(n/logn)nO(1) time algorithm violates the Exponential Time Hypothesis (ETH). Our approach combines tools developed for planar subgraph isomorphism such as ‘efficient inclusion-exclusion’ from Nederlof (2020) [15], and ‘isomorphisms checks’ from Bodlaender et al. (2016) [5] with a different separator hierarchy and a new bound on the number of non-isomorphic separations tailored for unit disk graphs. |
| Document Type: |
article in journal/newspaper |
| File Description: |
application/pdf |
| Language: |
English |
| ISSN: |
0022-0000 |
| Relation: |
https://dspace.library.uu.nl/handle/1874/474081 |
| Availability: |
https://dspace.library.uu.nl/handle/1874/474081 |
| Rights: |
info:eu-repo/semantics/OpenAccess |
| Accession Number: |
edsbas.BBD59DBB |
| Database: |
BASE |