Incremental Edge Orientation in Forests

For any forest $G = (V, E)$ it is possible to orient the edges $E$ so that no vertex in $V$ has out-degree greater than $1$. This paper considers the incremental edge-orientation problem, in which the edges $E$ arrive over time and the algorithm must maintain a low-out-degree edge orientation at all times. We give an algorithm that maintains a maximum out-degree of $3$ while flipping at most $O(log log n)$ edge orientations per edge insertion, with high probability in $n$. The algorithm requires worst-case time $O(log n log log n)$ per insertion, and takes amortized time $O(1)$. The previous state of the art required up to $O(log n / log log n)$ edge flips per insertion. We then apply our edge-orientation results to the problem of dynamic Cuckoo hashing. The problem of designing simple families $mathcal{H}$ of hash functions that are compatible with Cuckoo hashing has received extensive attention. These families $mathcal{H}$ are known to satisfy emph{static guarantees}, but do not come typically with emph{dynamic guarantees} for the running time of inserts and deletes. We show how to transform static guarantees (for $1$-associativity) into near-state-of-the-art dynamic guarantees (for $O(1)$-associativity) in a black-box fashion. Rather than relying on the family $mathcal{H}$ to supply randomness, as in past work, we instead rely on randomness within our table-maintenance algorithm.