Algorithms and Turing kernels for detecting and counting small patterns in unit disk graphs

Jesper Nederlof, Krisztina Szilágyi*

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

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/log⁡k)nO(1) time algorithm for counting pattern occurrences. We show this is tight, even for ply p=2: any 2o(n/log⁡n)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 languageEnglish
Article number103600
Number of pages13
JournalJournal of Computer and System Sciences
Volume148
DOIs
Publication statusPublished - Mar 2025

Bibliographical note

Publisher Copyright:
© 2024 The Author(s)

Keywords

  • Parameterized complexity
  • Subgraph isomorphism
  • Unit disk graphs

Fingerprint

Dive into the research topics of 'Algorithms and Turing kernels for detecting and counting small patterns in unit disk graphs'. Together they form a unique fingerprint.

Cite this