Counting Connected Subgraphs with Maximum-Degree-Aware Sieving
(2018) 29th International Symposium on Algorithms and Computation, ISAAC 2018p.1-17
- 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... (More)
- 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]. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/188143b5-4842-494d-b15b-39ffd6961a90
- author
- Björklund, Andreas LU ; Husfeldt, Thore LU ; Kaski, Petteri and Koivisto, Mikko
- organization
- publishing date
- 2018
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- keywords
- graph embedding, k-path, subgraph counting, maximum degree
- host publication
- 29th International Symposium on Algorithms and Computation (ISAAC 2018)
- pages
- 1 - 17
- publisher
- Schloss Dagstuhl - Leibniz-Zentrum für Informatik
- conference name
- 29th International Symposium on Algorithms and Computation, ISAAC 2018<br/><br/>
- conference location
- Jiaoxi, Yilan, Taiwan
- conference dates
- 2018-12-16 - 2018-12-19
- external identifiers
-
- scopus:85063676476
- ISBN
- 978-3-95977-094-1
- DOI
- 10.4230/LIPIcs.ISAAC.2018.17
- language
- English
- LU publication?
- yes
- id
- 188143b5-4842-494d-b15b-39ffd6961a90
- date added to LUP
- 2019-02-01 08:35:06
- date last changed
- 2022-03-25 07:55:33
@inproceedings{188143b5-4842-494d-b15b-39ffd6961a90, 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].}}, author = {{Björklund, Andreas and Husfeldt, Thore and Kaski, Petteri and Koivisto, Mikko}}, booktitle = {{29th International Symposium on Algorithms and Computation (ISAAC 2018)}}, isbn = {{978-3-95977-094-1}}, keywords = {{graph embedding; k-path; subgraph counting; maximum degree}}, language = {{eng}}, pages = {{1--17}}, publisher = {{Schloss Dagstuhl - Leibniz-Zentrum für Informatik}}, title = {{Counting Connected Subgraphs with Maximum-Degree-Aware Sieving}}, url = {{http://dx.doi.org/10.4230/LIPIcs.ISAAC.2018.17}}, doi = {{10.4230/LIPIcs.ISAAC.2018.17}}, year = {{2018}}, }