Marek Sokołowski, Strongly Polynomial Parallel Work-Depth Tradeoffs for Directed SSSP
2026-02-24 16:30 - 17:30 (Asia/Seoul) | Room B332, IBS (기초과학연구원)
In this talk, we show new strongly polynomial work-depth tradeoffs for computing single-source shortest paths (SSSP) in non-negatively weighted directed graphs in parallel. Most importantly, we prove that directed SSSP can be solved within $widetilde{O}(m+n^{2-varepsilon})$ work and $widetilde{O}(n^{1-varepsilon})$ depth for some positive $varepsilon>0$. For dense graphs with non-negative real weights, this yields the first nearly work-efficient strongly polynomial algorithm with sublinear depth. Moreover, we develop efficient parallel algorithms in the Word RAM model for several variants of SSSP in graphs with exponentially large edge weights.
This is a joint work with Adam Karczmarz and Wojciech Nadara.

Chính T. Hoàng, Problems on graph coloring
2026-03-03 16:30 - 17:30
A k-coloring of a graph is an assignment of k colors to its vertices such that no two adjacent adjacent vertices receive the same color. The Coloring Problem is the problem of determining the smallest k such that the graph admits a k-coloring. Given a set L of graphs, a graph G is L-free if G does not contain any graph in L as an induced subgraph. The complexity of the Coloring Problem for L-free graphs is known (NP-complete or polynomial-time solvable) whenever L contains a single graph. There has been keen interest in coloring graphs whose forbidden list L contains basic graphs such as induced paths, induced cycles and their complements. In this talk, I will provide a survey of recent progress on this topic.

Dario Cavallaro, TBA
2026-03-10 16:30 - 17:30

Hidde Koerts, TBA
2026-03-24 16:30 - 17:30

Tung H. Nguyen, TBA
2026-03-31 16:30 - 17:30

Mamadou Moustapha Kanté, TBA
2026-04-07 16:30 - 17:30

Xavier Goaoc, TBA
2026-05-19 16:30 - 17:30

Sarah Morell, Unsplittable Transshipments
2026-05-26 16:30 - 17:30
We consider an arc-capacitated directed graph $D=(V,A)$, where each node $v$ is associated with a rational balance value $b(v)$. Nodes with negative balance values are referred to as sources, while those with positive balance values are called sinks. A feasible $b$-transshipment is a flow $f : A to mathbb{R}_{ge 0}$ that routes the total supply of the sources to the sinks through $D$, while respecting the given arc capacity constraints and satisfying the balance requirements at each node. An unsplittable $b$-transshipment additionally requires that, for each source-sink pair, the flow sent from that source to that sink is routed along at most one directed path. Unsplittable $b$-transshipments (UT) generalize the well-studied single source unsplittable flow (SSUF) problem in which $D$ contains a single source and multiple sinks, and each demand must be routed along a single path from the common source to its destination.
Given a feasible $b$-transshipment $f$ that is not necessarily unsplittable, a natural question is whether there exists an feasible unsplittable $b$-transshipment flow $g$ that approximates $f$ in an arc-wise sense. In particular, we seek bounds on the maximum deviation $|f_a-g_a|$ over all arcs $a in A$. For the special case of SSUFs, Dinitz, Garg, and Goemans (Combinatorica 1999) proved that there exists an unsplittable flow $g$ such that $g_a leq f_a + d_{max}$ for all $a in A$, where $d_{max}$ denotes the maximum demand value. Jointly with Martin Skutella (Mathematical Programming 2022), we studied unsplittable flows with arc-wise lower bounds and showed that there exists an unsplittable flow $g$ satisfying $g_a ge f_a – d_{max}$ for all $a in A$.
In this talk, we extend this line of research by adapting the techniques of Dinitz, Garg, and Goemans to the more general setting of UTs. We show that, given any feasible $b$-transshipment $f$, there exists a feasible unsplittable $b$-transshipment $g$ such that $g_a leq f_a + d_{max}$ (resp. $g_a ge f_a – d_{max}$) for all $a in A$.
This is joint work with Srinwanti Debgupta and Martin Skutella.

Maria Chudnovsky, TBA
2026-06-02 16:30 - 17:30

Martin Milanič, TBA
2026-06-09 16:30 - 17:30
