Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Counting Connected Subgraphs with Maximum-Degree-Aware Sieving

Björklund, Andreas LU ; Husfeldt, Thore LU ; Kaski, Petteri and Koivisto, Mikko (2018) 29th International Symposium on Algorithms and Computation, ISAAC 2018

 p.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:
author
; ; and
organization
publishing date
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 &lt;= 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&lt;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}},
}