Counting Connected Subgraphs with Maximum-Degree-Aware Sieving
Loading...
Access rights
openAccess
URL
Journal Title
Journal ISSN
Volume Title
A4 Artikkeli konferenssijulkaisussa
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
Date
2018
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
1-12
Series
29th International Symposium on Algorithms and Computation (ISAAC 2018), Leibniz International Proceedings in Informatics (LIPIcs), Volume 123
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].Description
Keywords
graph embedding, k-path, subgraph counting, maximum degree
Other note
Citation
Björklund, A, Husfeldt, T, Kaski, P & Koivisto, M 2018, Counting Connected Subgraphs with Maximum-Degree-Aware Sieving . in W-L Hsu, D-T Lee & C-S Liao (eds), 29th International Symposium on Algorithms and Computation (ISAAC 2018) ., 17, Leibniz International Proceedings in Informatics (LIPIcs), vol. 123, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Dagstuhl, Germany, pp. 1-12, International Symposium on Algorithms and Computation, Jiaoxi, Taiwan, Republic of China, 16/12/2018 . https://doi.org/10.4230/LIPIcs.ISAAC.2018.17