@inbook{dcce17cf57ed42b3b47b69f85794b192,

title = "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 {\textquoteleft}efficient inclusion-exclusion{\textquoteright} from [Nederlof STOC{\textquoteright}20], and {\textquoteleft}isomorphisms checks{\textquoteright} from [Bodlaender et al. ICALP{\textquoteright}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.",

keywords = "Parameterized complexity, Subgraph isomorphism, Unit disk graphs",

author = "Jesper Nederlof and Krisztina Szil{\'a}gyi",

note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.",

year = "2024",

month = jan,

day = "21",

doi = "10.1007/978-3-031-52113-3_29",

language = "English",

isbn = "978-3-031-52112-6",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "413–426",

editor = "Fernau, {Henning } and Serge Gaspers and Klasing, {Ralf }",

booktitle = "SOFSEM 2024: Theory and Practice of Computer Science",

edition = "1",

}