On Friday, 25 September 2026 Yonggang Jiang defended his thesis with the title: “Graph Projections for Fast Graph Algorithms”. Since October 2021 he was PhD student in Computer Science at Saarland University in Saarbrücken and the Max Planck Institute for Informatics under the supervision of Prof. Danupon Na Nongkai, head of department Algorithms and Complexity. The doctoral degree is awarded by Saarland University.
Abstract of the thesis:
We develop graph projection techniques for designing fast graph algorithms. Instead of simplifying an input graph on the same vertex set, we expand it into a larger auxiliary graph with simpler structure, solve the problem there, and project the solution back. This viewpoint leads to four main contributions: DAG projections for distance, flow, and cut problems, yielding an almost-linear-time combinatorial algorithm for minimum-cost flow on dense graphs; path covers, which give the first deterministic near-linear-time algorithm for negative-weight shortest paths; common-neighborhood clustering, which closes the deterministic–randomized complexity gap for global minimum vertex cut and gives new parallel and distributed algorithms; and Steiner shortcuts, which suggest a possible route around known barriers for shortcuts in directed graphs. Together, these results demonstrate that expanding a graph into a larger but more structured object can be a powerful principle for algorithm design.