Parameterised and fine-grained subgraph counting, modulo 2
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 ⊕...
| Main Authors: | , |
|---|---|
| Format: | Conference item |
| Language: | English |
| Published: |
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
2023
|
| _version_ | 1826310850443476992 |
|---|---|
| author | Goldberg, L Roth, M |
| author_facet | Goldberg, L Roth, M |
| author_sort | Goldberg, L |
| collection | OXFORD |
| description | 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).<br>
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.<br>
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). |
| first_indexed | 2024-03-07T07:59:35Z |
| format | Conference item |
| id | oxford-uuid:d27f72b8-97a6-4962-8a22-24601e2d7c42 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T07:59:35Z |
| publishDate | 2023 |
| publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
| record_format | dspace |
| spelling | oxford-uuid:d27f72b8-97a6-4962-8a22-24601e2d7c422023-09-06T11:35:44ZParameterised and fine-grained subgraph counting, modulo 2Conference itemhttp://purl.org/coar/resource_type/c_5794uuid:d27f72b8-97a6-4962-8a22-24601e2d7c42EnglishSymplectic ElementsSchloss Dagstuhl - Leibniz-Zentrum für Informatik2023Goldberg, LRoth, MGiven 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).<br> 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.<br> 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). |
| spellingShingle | Goldberg, L Roth, M Parameterised and fine-grained subgraph counting, modulo 2 |
| title | Parameterised and fine-grained subgraph counting, modulo 2 |
| title_full | Parameterised and fine-grained subgraph counting, modulo 2 |
| title_fullStr | Parameterised and fine-grained subgraph counting, modulo 2 |
| title_full_unstemmed | Parameterised and fine-grained subgraph counting, modulo 2 |
| title_short | Parameterised and fine-grained subgraph counting, modulo 2 |
| title_sort | parameterised and fine grained subgraph counting modulo 2 |
| work_keys_str_mv | AT goldbergl parameterisedandfinegrainedsubgraphcountingmodulo2 AT rothm parameterisedandfinegrainedsubgraphcountingmodulo2 |