Sökning: id:"swepub:oai:lup.lub.lu.se:188143b5-4842-494d-b15b-39ffd6961a90" >
Counting Connected ...
Counting Connected Subgraphs with Maximum-Degree-Aware Sieving
-
- Björklund, Andreas (författare)
- Lund University,Lunds universitet,Institutionen för datavetenskap,Institutioner vid LTH,Lunds Tekniska Högskola,Department of Computer Science,Departments at LTH,Faculty of Engineering, LTH
-
- Husfeldt, Thore (författare)
- Lund University,Lunds universitet,Institutionen för datavetenskap,Institutioner vid LTH,Lunds Tekniska Högskola,Department of Computer Science,Departments at LTH,Faculty of Engineering, LTH,IT University of Copenhagen
-
- Kaski, Petteri (författare)
- Aalto University
-
visa fler...
-
- Koivisto, Mikko (författare)
- University of Helsinki
-
visa färre...
-
(creator_code:org_t)
- 2018
- 2018
- Engelska.
-
Ingår i: 29th International Symposium on Algorithms and Computation (ISAAC 2018). - 9783959770941 ; , s. 1-17
- Relaterad länk:
-
http://dx.doi.org/10... (free)
-
visa fler...
-
https://lup.lub.lu.s...
-
https://doi.org/10.4...
-
visa färre...
Abstract
Ämnesord
Stäng
- 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].
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Nyckelord
- graph embedding
- k-path
- subgraph counting
- maximum degree
Publikations- och innehållstyp
- kon (ämneskategori)
- ref (ämneskategori)
Hitta via bibliotek
Till lärosätets databas