A fundamental graph problem asks to compute the number of induced copies of a k-node pattern graph H in an n-node graph G. The fastest algorithm to date is still the 35-years-old algorithm by Nešetřil and Poljak [28], with running time f(k) · O(nωb k3 c+2) where ω ≤ 2.373 is the matrix multiplication exponent. In this work we show that, if one takes into account the degeneracy d of G, then the picture becomes substantially richer and leads to faster algorithms when G is sufficiently sparse. More precisely, after introducing a novel notion of graph width, the DAG-treewidth, we prove what follows. If H has DAG-treewidth τ(H) and G has degeneracy d, then the induced copies of H in G can be counted in time f(d, k) · Õ(nτ(H)); and, under the Exponential Time Hypothesis, no algorithm can solve the problem in time f(d, k) · no(τ(H)/ ln τ(H)) for all H. This result characterises the complexity of counting subgraphs in a d-degenerate graph. Developing bounds on τ(H), then, we obtain natural generalisations of classic results and faster algorithms for sparse graphs. For example, when d = O(poly log(n)) we can count the induced copies of any H in time f(k) · Õ(nb k4 c+2), beating the Nešetřil-Poljak algorithm by essentially a cubic factor in n.

Faster subgraph counting in sparse graphs / M. Bressan (LEIBNIZ INTERNATIONAL PROCEEDINGS IN INFORMATICS). - In: Leibniz International Proceedings in Informatics, LIPIcs / [a cura di] B.M.P. Jansen, J.A. Telle. - [s.l] : Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2019. - ISBN 978-395977129-0. - pp. 6:1-6:15 (( Intervento presentato al 14. convegno International Symposium on Parameterized and Exact Computation, IPEC tenutosi a Munich nel 2019 [10.4230/LIPIcs.IPEC.2019.6].

Faster subgraph counting in sparse graphs

M. Bressan
2019

Abstract

A fundamental graph problem asks to compute the number of induced copies of a k-node pattern graph H in an n-node graph G. The fastest algorithm to date is still the 35-years-old algorithm by Nešetřil and Poljak [28], with running time f(k) · O(nωb k3 c+2) where ω ≤ 2.373 is the matrix multiplication exponent. In this work we show that, if one takes into account the degeneracy d of G, then the picture becomes substantially richer and leads to faster algorithms when G is sufficiently sparse. More precisely, after introducing a novel notion of graph width, the DAG-treewidth, we prove what follows. If H has DAG-treewidth τ(H) and G has degeneracy d, then the induced copies of H in G can be counted in time f(d, k) · Õ(nτ(H)); and, under the Exponential Time Hypothesis, no algorithm can solve the problem in time f(d, k) · no(τ(H)/ ln τ(H)) for all H. This result characterises the complexity of counting subgraphs in a d-degenerate graph. Developing bounds on τ(H), then, we obtain natural generalisations of classic results and faster algorithms for sparse graphs. For example, when d = O(poly log(n)) we can count the induced copies of any H in time f(k) · Õ(nb k4 c+2), beating the Nešetřil-Poljak algorithm by essentially a cubic factor in n.
Degeneracy; Subgraph counting; Tree decomposition
Settore INF/01 - Informatica
Book Part (author)
File in questo prodotto:
File Dimensione Formato  
Bressan&2019-IPEC.pdf

accesso aperto

Tipologia: Publisher's version/PDF
Dimensione 766.98 kB
Formato Adobe PDF
766.98 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/922311
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? ND
social impact