Björklund, Andreas ;
Husfeldt, Thore ;
Kaski, Petteri ;
Koivisto, Mikko
Counting Connected Subgraphs with MaximumDegreeAware Sieving
Abstract
We study the problem of counting the isomorphic occurrences of a kvertex pattern graph P as a subgraph in an nvertex host graph G. Our specific interest is on algorithms for subgraph counting that are sensitive to the maximum degree Delta of the host graph.
Assuming that the pattern graph P is connected and admits a vertex balancer of size b, we present an algorithm that counts the occurrences of P in G in O ((2 Delta2)^{(k+b)/2} 2^{b} n/(Delta) k^2 log n) time. We define a balancer as a vertex separator of P that can be represented as an intersection of two equalsize vertex subsets, the union of which is the vertex set of P, and both of which induce connected subgraphs of P.
A corollary of our main result is that we can count the number of kvertex paths in an nvertex graph in O((2 Delta2)^{floor[k/2]} n k^2 log n) time, which for all moderately dense graphs with Delta <= n^{1/3} improves on the recent breakthrough work of Curticapean, Dell, and Marx [STOC 2017], who show how to count the isomorphic occurrences of a qedge pattern graph as a subgraph in an nvertex host graph in time O(q^q n^{0.17q}) for all large enough q. Another recent result of Brand, Dell, and Husfeldt [STOC 2018] shows that kvertex paths in a boundeddegree graph can be approximately counted in O(4^kn) time. Our result shows that the exact count can be recovered at least as fast for Delta<10.
Our algorithm is based on the principle of inclusion and exclusion, and can be viewed as a sparsitysensitive version of the "counting in halves"approach explored by Björklund, Husfeldt, Kaski, and Koivisto [ESA 2009].
BibTeX  Entry
@InProceedings{bjrklund_et_al:LIPIcs:2018:9965,
author = {Andreas Bj{\"o}rklund and Thore Husfeldt and Petteri Kaski and Mikko Koivisto},
title = {{Counting Connected Subgraphs with MaximumDegreeAware Sieving}},
booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)},
pages = {17:117:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770941},
ISSN = {18688969},
year = {2018},
volume = {123},
editor = {WenLian Hsu and DerTsai Lee and ChungShou Liao},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9965},
URN = {urn:nbn:de:0030drops99655},
doi = {10.4230/LIPIcs.ISAAC.2018.17},
annote = {Keywords: graph embedding, kpath, subgraph counting, maximum degree}
}
06.12.2018
Keywords: 

graph embedding, kpath, subgraph counting, maximum degree 
Seminar: 

29th International Symposium on Algorithms and Computation (ISAAC 2018)

Issue date: 

2018 
Date of publication: 

06.12.2018 