Abstract
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.
Original language | English |
---|---|
Article number | 103600 |
Number of pages | 13 |
Journal | Journal of Computer and System Sciences |
Volume | 148 |
DOIs | |
Publication status | Published - Mar 2025 |
Bibliographical note
Publisher Copyright:© 2024 The Author(s)
Keywords
- Parameterized complexity
- Subgraph isomorphism
- Unit disk graphs