Special Seminar - Markus Blumenstock

Title: Orientations, Pseudoforests, Flows, and the Densest Subgraph
 

Abstract:

Given an undirected graph, consider the problem of finding an orientation such that the max-imum indegree is minimized. The Gabow-Westermann algorithm can solve it by exploiting the matroid structure of pseudoforests. I will show that its runtime can be improved to {O}(|E|^{1.5} \sqrt{\log \log |V|) by using Kowalik's approximation scheme, and better bounds can be given under certain conditions. In the process, we shall see and exploit the problem's relationship to the densest subgraph problem. I will then discuss some open questions, most notably whether an approximation ratio of less than 2 can be obtained in linear time. I will demonstrate two minor results in this direction: a small modification of Kowalik's scheme yields a (1+ε)-approximation in time {O}(|E|\log |V|) for every fixed ε>0, and the 2-approximation algorithm of Asahiro et al. can be implemented in linear time.