TY - GEN

T1 - Balanced families of perfect hash functions and their applications

AU - Alon, Noga

AU - Gutner, Shai

PY - 2007

Y1 - 2007

N2 - The construction of perfect hash functions is a well-studied topic. In this paper, this concept is generalized with the following definition. We say that a family of functions from [n] to [k] is a δ-balanced (n, k)-family of perfect hash functions if for every S ⊆ [n], |S| = k, the number of functions that are 1-1 on S is between T/δ and ST 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, k)-family of perfect hash functions of size 2O(k log log k) log n can be constructed in time 2O(k log log k) 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 k for any k ≤ O(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 paper, this concept is generalized with the following definition. We say that a family of functions from [n] to [k] is a δ-balanced (n, k)-family of perfect hash functions if for every S ⊆ [n], |S| = k, the number of functions that are 1-1 on S is between T/δ and ST 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, k)-family of perfect hash functions of size 2O(k log log k) log n can be constructed in time 2O(k log log k) 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 k for any k ≤ O(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=38149059721&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=38149059721&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-73420-8_39

DO - 10.1007/978-3-540-73420-8_39

M3 - Conference contribution

AN - SCOPUS:38149059721

SN - 3540734198

SN - 9783540734192

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 435

EP - 446

BT - Automata, Languages and Programming - 34th International Colloquium, ICALP 2007, Proceedings

PB - Springer Verlag

T2 - 34th International Colloquium on Automata, Languages and Programming, ICALP 2007

Y2 - 9 July 2007 through 13 July 2007

ER -