Research Group Algorithmics and Computational ComplexityTalk 21.06.2018

# Parameterized Algorithms for Network Flows

Leon Kellerhals (TU Berlin)

Computing maximum flows in directed graphs is one of the most fundamental and applied network flow problems. For graphs with $m$ arcs, $n$ vertices and capacities of size at most $C$, Lee and Sidford [FOCS '14] provided an $\tilde{O}(m \sqrt{n} \log^2 C)$-time algorithm, but for several applications this time is still too slow.

In the spirit of the FPT in P program introduced by Giannopoulou et al. [Theoretical Computer Science '17] this work analyzes parameterizations for Maximum Flow. Our results are of two kinds. One the one hand, we show that many parameters such as maximum degree or the vertex deletion distance to complete graphs do not help to solve the problem more quickly. On the other hand we provide "good news": First, we provide quasilinear-time applicable data reduction rules that yield a kernel of size linear in the undirected feedback edge number (i.e., the edge deletion distance from the undirected input graph to forests). This is, to the best of our knowledge, the first nontrivial kernelization result for Maximum Flow. Second, we introduce a systematic approach for designing fixed-parameter algorithms for Maximum Flow. This approach is based on ideas by Hochstein and Weihe [SODA '07] and generalizes the Push-Relabel method by Goldberg and Tarjan [Journal of the ACM '88]. By applying our approach with the underlying feedback vertex number $k$ (i.e., the vertex deletion distance from the undirected input graph to forests) we can solve the problem in $\tilde{O}(k^4 m)$ time.

Date
Speaker
Location
Language
21.06.2018
16:15
Leon Kellerhals
TEL 512
English

Back to the research colloquium site.

To top