Fast Algorithms for Pseudoarboricity.

The densest subgraph problem, which asks for a subgraph with the maximum edges-to-vertices ratio d∗, is solvable in polynomial time. We discuss algorithms for this problem and the computation of a graph orientation with the lowest maximum indegree, which is equal to ⌈d∗⌉. This value also equals the pseudoarboricity of the graph. We show that it can be computed in O(|E| √ log log d∗) time, and that better estimates can be given for graph classes where d∗ satisfies certain asymptotic bounds. These runtimes are achieved by accelerating a binary search with an approximation scheme, and a runtime analysis of Dinitz’s algorithm on flow networks where all arcs, except the source and sink arcs, have unit capacity. We experimentally compare implementations of various algorithms for the densest subgraph and pseudoarboricity problems. In flow-based algorithms, Dinitz’s algorithm performs significantly better than push-relabel algorithms on all instances tested.