We study the problems of counting the homomorphisms, the copies, and the induced copies of a k-vertex graph H in a d-degenerate n-vertex graph G. By leveraging a new family of graph-minor obstructions called F-gadgets, we establish explicit and exhaustive complexity classifications for counting copies and induced copies. For instance., we show that the copies of H in G can be counted in time f(k, d)nmax(1,mathsf{imn(H)} log n, where f is some computable function and imn (H) is the size of the largest induced matching of H; and that whenever the class of allowed patterns has arbitrarily large induced matchings, no algorithm runs in time f(k, d)n o(mathsf{imn(H)/logmathsf{imn(H) for any function f, unless the Exponential Time Hypothesis fails. A similar result holds for counting induced copies, with the independence number α(H) in place of imn(H). These results imply complexity dichotomies, into fixed-parameter tractable versus #W[1]-hard cases, which parallel the well-known dichotomies when d is not a parameter. Our results also imply the #W[1]-hardness of counting several patterns, such as k-matchings and k-trees, in d-degenerate graphs. We also give new hardness results and approximation algorithms for generalized pattern counting (i.e., counting patterns with a given property) in degenerate graphs.

Exact and Approximate Pattern Counting in Degenerate Graphs: New Algorithms, Hardness Results, and Complexity Dichotomies / M. Bressan, M. Roth - In: 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)[s.l] : IEEE, 2022. - ISBN 978-1-6654-2055-6. - pp. 276-285 (( Intervento presentato al 62. convegno IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021 tenutosi a Denver nel 2022 [10.1109/FOCS52979.2021.00036].

Exact and Approximate Pattern Counting in Degenerate Graphs: New Algorithms, Hardness Results, and Complexity Dichotomies

M. Bressan;
2022

Abstract

We study the problems of counting the homomorphisms, the copies, and the induced copies of a k-vertex graph H in a d-degenerate n-vertex graph G. By leveraging a new family of graph-minor obstructions called F-gadgets, we establish explicit and exhaustive complexity classifications for counting copies and induced copies. For instance., we show that the copies of H in G can be counted in time f(k, d)nmax(1,mathsf{imn(H)} log n, where f is some computable function and imn (H) is the size of the largest induced matching of H; and that whenever the class of allowed patterns has arbitrarily large induced matchings, no algorithm runs in time f(k, d)n o(mathsf{imn(H)/logmathsf{imn(H) for any function f, unless the Exponential Time Hypothesis fails. A similar result holds for counting induced copies, with the independence number α(H) in place of imn(H). These results imply complexity dichotomies, into fixed-parameter tractable versus #W[1]-hard cases, which parallel the well-known dichotomies when d is not a parameter. Our results also imply the #W[1]-hardness of counting several patterns, such as k-matchings and k-trees, in d-degenerate graphs. We also give new hardness results and approximation algorithms for generalized pattern counting (i.e., counting patterns with a given property) in degenerate graphs.
counting problems; degenerate graphs; fine-grained complexity theory; parameterized algorithms
Settore INF/01 - Informatica
IEEE Computer Society Technical Committee on Mathematical Foundations of Computing
Book Part (author)
File in questo prodotto:
File Dimensione Formato  
2103.05588.pdf

accesso aperto

Tipologia: Pre-print (manoscritto inviato all'editore)
Dimensione 612.3 kB
Formato Adobe PDF
612.3 kB Adobe PDF Visualizza/Apri
Exact_and_Approximate_Pattern_Counting_in_Degenerate_Graphs_New_Algorithms_Hardness_Results_and_Complexity_Dichotomies.pdf

accesso aperto

Tipologia: Publisher's version/PDF
Dimensione 396.56 kB
Formato Adobe PDF
396.56 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/922295
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 0
social impact