Balanced families of perfect hash functions and their applications

DOI10.1145/1798596.1798607MaRDI QIDQ2930337zbMATH OpenOpenAlexFDO

Authors Noga Alon, Shai Gutner

Publication date 18 November 2014

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0805.4300

zbMATH Keywords

color-codingperfect hashingapproximate counting of subgraphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Abstract: 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 $delta$-balanced $(n,k)$-family of perfect hash functions if for every $Ssubseteq[n]$, $|S|=k$, the number of functions that are 1-1 on $S$ is between $T/delta$ and $deltaT$ 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 $delta$ to be close to 1) for every such $S$. Our main result is that for any constant $delta>1$, a $delta$-balanced $(n,k)$-family of perfect hash functions of size $2^{O(kloglogk)}logn$ can be constructed in time $2^{O(kloglogk)}nlogn$. 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 $kleqO(fraclognlogloglogn)$ in a graph with $n$ vertices. The approximation is up to any fixed desirable relative error.

Recommendations

• Balanced Families of Perfect Hash Functions and Their Applications
• Balanced hashing, color coding and approximate counting
• Perfect hash families: Probabilistic methods and explicit constructions
• Simple and Space-Efficient Minimal Perfect Hash Functions
• Constructing Perfect Hash Families Using a Greedy Algorithm

Cited in

(11)

• The \(k\)-distinct language: parameterized automata constructions
• Approximate Counting of k-Paths: Deterministic and in Polynomial Space
• Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle
• The Budgeted Unique Coverage Problem and Color-Coding
• Counting problems in parameterized complexity
• Faster algorithms for finding and counting subgraphs
• Tensor network complexity of multilinear maps
• Counting connected subgraphs with maximum-degree-aware sieving
• Balanced Families of Perfect Hash Functions and Their Applications
• Balanced hashing, color coding and approximate counting
• The challenges of unbounded treewidth in parameterised subgraph counting problems

This page was built for publication: Balanced families of perfect hash functions and their applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2930337)