TY - JOUR
T1 - Balanced families of perfect hash functions and their applications
AU - Alon, Noga
AU - Gutner, Shai
N1 - Copyright:
Copyright 2010 Elsevier B.V., All rights reserved.
PY - 2010/6/1
Y1 - 2010/6/1
N2 - The construction of perfect hash functions is a well-studied topic. In this article, this concept is generalized with the following definition. We say that a family of functions from [n] to [κ] is a δ-balanced (n, κ)-family of perfect hash functions if for every S ⊆ [n], |S| = κ, the number of functions that are 1-1 on S is between T/δ and δT for some constant T > 0. The standard definition of a family of perfect hash functions requires that there will be at least one function that is 1-1 on S, for each S of size k. In the new notion of balanced families, we require the number of 1-1 functions to be almost the same (taking δ to be close to 1) for every such S. Our main result is that for any constant δ > 1, a δ-balanced (n, κ)-family of perfect hash functions of size 2O(κ log log κ) log n can be constructed in time 2O(κ log log κ)n log n. Using the technique of color-coding we can apply our explicit constructions to devise approximation algorithms for various counting problems in graphs. In particular, we exhibit a deterministic polynomial-time algorithm for approximating both the number of simple paths of length k and the number of simple cycles of size κ for any κ ≤ 0(log n/log log log n) in a graph with n vertices. The approximation is up to any fixed desirable relative error.
AB - The construction of perfect hash functions is a well-studied topic. In this article, this concept is generalized with the following definition. We say that a family of functions from [n] to [κ] is a δ-balanced (n, κ)-family of perfect hash functions if for every S ⊆ [n], |S| = κ, the number of functions that are 1-1 on S is between T/δ and δT for some constant T > 0. The standard definition of a family of perfect hash functions requires that there will be at least one function that is 1-1 on S, for each S of size k. In the new notion of balanced families, we require the number of 1-1 functions to be almost the same (taking δ to be close to 1) for every such S. Our main result is that for any constant δ > 1, a δ-balanced (n, κ)-family of perfect hash functions of size 2O(κ log log κ) log n can be constructed in time 2O(κ log log κ)n log n. Using the technique of color-coding we can apply our explicit constructions to devise approximation algorithms for various counting problems in graphs. In particular, we exhibit a deterministic polynomial-time algorithm for approximating both the number of simple paths of length k and the number of simple cycles of size κ for any κ ≤ 0(log n/log log log n) in a graph with n vertices. The approximation is up to any fixed desirable relative error.
KW - Approximate counting of subgraphs
KW - Color-coding
KW - Perfect hashing
UR - http://www.scopus.com/inward/record.url?scp=77954392637&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77954392637&partnerID=8YFLogxK
U2 - 10.1145/1798596.1798607
DO - 10.1145/1798596.1798607
M3 - Article
AN - SCOPUS:77954392637
VL - 6
JO - ACM Transactions on Algorithms
JF - ACM Transactions on Algorithms
SN - 1549-6325
IS - 3
M1 - 54
ER -