Andreas Grigorjew - How to decompose a flow?

Speaker: Andreas Grigorjew

Title: How to decompose a flow?

Room: B428

Date: 10/04/2025 14:00

Every flow on a digraph can be decomposed into paths due to flow conservation at all internal nodes. The Minimum Flow Decomposition (MFD) problem, which is strongly NP-hard, involves finding the smallest set of weighted paths in a digraph G whose total weight equals a given flow on G. This problem is crucial in various fields, including transportation planning, network communication, and bioinformatics, which has driven the development of fast heuristic algorithms. Despite its proximity to graph decompositions and its broad applications, MFD has received surprisingly little attention in the theoretical cs community.

In this talk, I will provide an overview of the current theoretical understanding of MFD on DAGs. We will consider the DAG width—the minimum number of paths required to cover all edges—as a natural lower bound for MFD, and demonstrate its importance in the problem. Further, we will show how the decomposition of positive flows naturally leads to a notion of directed graph minors, introducing a new concept of hereditary width and linking it to the parallel-width of a DAG (the largest minimal s-t edge cut-set) [Deligkas and Meir, MFCS 2018]. Using these parameters, we can, for the first time, provide a theoretical analysis of existing heuristics and present improved parameterized complexity results.