M.Sc. Andreas Grigorjew defends his doctoral thesis "Algorithms and Graph Structures for Splitting Network Flows, in Theory and Practice" on Wednesday the 19th of February 2025 at 13 o'clock in the University of Helsinki Exactum building, Auditorium A111 (Pietari Kalmin katu 5, 1st floor). His opponent is Professor László A. Végh (University of Bonn, Germany) and custos Associate Professor Alexandru I. Tomescu (University of Helsinki). The defence will be held in English.
The thesis of Andreas Grigorjew is a part of research done in the Department of Computer Science and in the Graph Algorithms team of the Algorithmic Bioinformatics group at the University of Helsinki. His supervisor has been Associate Professor Alexandru I. Tomescu (University of Helsinki).
Algorithms and Graph Structures for Splitting Network Flows, in Theory and Practice
Flows on directed graphs measure the number of units that travel between nodes in a network, which naturally models the movement of a commodity. Moreover, a common theme in graph theory is the decomposition of complex objects into simpler ones, as this enables us to work separately with each of the simple objects. Although a vast amount of research handles the computation of flows, a relatively small amount of work addresses their decomposition, despite the relevance of both flows and graph decompositions in theory and applications.
In this thesis, we study the Minimum Flow Decomposition (MFD) problem, which is about finding a smallest set of weighted paths whose superposition is equal to an integral input flow. It is a fundamental optimisation problem that is NP-hard and has applications in various fields, such as Bioinformatics, communication networks or transportation planning. We study the problem on directed acyclic graphs (DAGs) for integer flows and consider two angles, a theoretical and a practical one. The DAG width, the fewest number of paths to cover all edges, plays a central role in both angles.
As many optimisation problems are NP-hard and are not feasibly solvable for many practical instances, heuristics are commonly used as a trade-off between optimality and runtime. Despite the active development of heuristics for MFD in the recent years, we have only gained little understanding of the theoretical aspects of the problem. In the first three papers, we analyse heuristics and their relationship to graph structure. We differentiate between two variants: allowing negative path weights and forcing them to be positive. In the former case, we present an approximation algorithm with performance guarantees for all instances. In the latter, we present performance guarantees for graphs that commonly appear in practice, and we analyse the computational complexity based on notions that are connected to the DAG width.
In the fourth paper, we use Integer Linear Programming (ILP) methods to improve the exact and heuristic solving of MFD. We improve the runtime of the current state-of-the-art exact ILP-based solver using pre-computation steps on the instances. Further, we define a new variant of MFD and show that it can be used as approximation to the original MFD problem, whose approximation performance improves compared to the current state-of-the-art heuristic by a large magnitude while still admitting an acceptable runtime on our datasets.
Availability of the dissertation
An electronic version of the doctoral dissertation will be available in the University of Helsinki open repository Helda at http://urn.fi/URN:ISBN:978-952-84-0770-6.
Printed copies will be available on request from Andreas Grigorjew: andreas.grigorjew@helsinki.fi.