License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2018.17
URN: urn:nbn:de:0030-drops-99655
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9965/
Björklund, Andreas ;
Husfeldt, Thore ;
Kaski, Petteri ;
Koivisto, Mikko
Counting Connected Subgraphs with Maximum-Degree-Aware Sieving
Abstract
We study the problem of counting the isomorphic occurrences of a k-vertex pattern graph P as a subgraph in an n-vertex 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 Delta-2)^{(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 equal-size 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 k-vertex paths in an n-vertex graph in O((2 Delta-2)^{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 q-edge pattern graph as a subgraph in an n-vertex 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 k-vertex paths in a bounded-degree 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 sparsity-sensitive 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 Maximum-Degree-Aware Sieving}},
booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)},
pages = {17:1--17:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-094-1},
ISSN = {1868-8969},
year = {2018},
volume = {123},
editor = {Wen-Lian Hsu and Der-Tsai Lee and Chung-Shou Liao},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9965},
URN = {urn:nbn:de:0030-drops-99655},
doi = {10.4230/LIPIcs.ISAAC.2018.17},
annote = {Keywords: graph embedding, k-path, subgraph counting, maximum degree}
}
|
Keywords: |
|
graph embedding, k-path, subgraph counting, maximum degree |
|
Collection: |
|
29th International Symposium on Algorithms and Computation (ISAAC 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
06.12.2018 |
