Parameterised and fine-grained subgraph counting, modulo 2

Conference item

Given a class of graphs ℋ, the problem ⊕Sub(ℋ) is defined as follows. The input is a graph H ∈ ℋ together with an arbitrary graph G. The problem is to compute, modulo 2, the number of subgraphs of G that are isomorphic to H. The goal of this research is to determine for which classes ℋ the problem ⊕Sub(ℋ) is fixed-parameter tractable (FPT), i.e., solvable in time f(|H|)⋅|G|^O(1).
Curticapean, Dell, and Husfeldt (ESA 2021) conjectured that ⊕Sub(ℋ) is FPT if and only if the class of allowed patterns ℋ is matching splittable, which means that for some fixed B, every H ∈ ℋ can be turned into a matching (a graph in which every vertex has degree at most 1) by removing at most B vertices.
Assuming the randomised Exponential Time Hypothesis, we prove their conjecture for (I) all hereditary pattern classes ℋ, and (II) all tree pattern classes, i.e., all classes ℋ such that every H ∈ ℋ is a tree. We also establish almost tight fine-grained upper and lower bounds for the case of hereditary patterns (I).

Authors: Goldberg, L; Roth, M

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
• Journal: Leibniz International Proceedings in Informatics
• Volume: 261
• Pages: 68:1-68:17
• Series: Leibniz International Proceedings in Informatics (LIPIcs)
• Place of publication: Dagstuhl, Germany
• Publication date: 2023-07-05
• Acceptance date: 2023-04-21
• Event title: 50th EATCS International Colloquium on Automata, Languages and Programming, ICALP 2023
• Event location: Paderborn, Germany
• Event website: https://icalp2023.cs.upb.de/
• Event start date: 2023-07-10
• Event end date: 2023-07-14
• DOI: 10.4230/LIPIcs.ICALP.2023.68
• ISSN: 1868-8969
• ISBN: 978-3-95977-278-5
• Language: English
• Keywords: modular counting; subgraph counting; parameterised complexity; FFR; fine-grained complexity