Bressan, Marco
Faster Subgraph Counting in Sparse Graphs
Abstract
A fundamental graph problem asks to compute the number of induced copies of a knode pattern graph H in an nnode graph G. The fastest algorithm to date is still the 35yearsold algorithm by Nesetril and Poljak [Nesetril and Poljak, 1985], with running time f(k) * O(n^{omega floor[k/3] + 2}) where omega <=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 DAGtreewidth, we prove what follows. If H has DAGtreewidth tau(H) and G has degeneracy d, then the induced copies of H in G can be counted in time f(d,k) * O~(n^{tau(H)}); and, under the Exponential Time Hypothesis, no algorithm can solve the problem in time f(d,k) * n^{o(tau(H)/ln tau(H))} for all H. This result characterises the complexity of counting subgraphs in a ddegenerate graph. Developing bounds on tau(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) * O~(n^{floor[k/4] + 2}), beating the NesetrilPoljak algorithm by essentially a cubic factor in n.
BibTeX  Entry
@InProceedings{bressan:LIPIcs:2019:11467,
author = {Marco Bressan},
title = {{Faster Subgraph Counting in Sparse Graphs}},
booktitle = {14th International Symposium on Parameterized and Exact Computation (IPEC 2019)},
pages = {6:16:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771290},
ISSN = {18688969},
year = {2019},
volume = {148},
editor = {Bart M. P. Jansen and Jan Arne Telle},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2019/11467},
URN = {urn:nbn:de:0030drops114673},
doi = {10.4230/LIPIcs.IPEC.2019.6},
annote = {Keywords: subgraph counting, tree decomposition, degeneracy}
}
04.12.2019
Keywords: 

subgraph counting, tree decomposition, degeneracy 
Seminar: 

14th International Symposium on Parameterized and Exact Computation (IPEC 2019)

Issue date: 

2019 
Date of publication: 

04.12.2019 