TBD
TBD
Finding a Steiner strongly $k$-arc-connected orientation is particularly relevant in network design and reliability, as it guarantees robust communication between a designated set of critical nodes. We consider a rooted variant, called the Steiner Rooted Orientation problem, where one is given an undirected graph on $n$ vertices, a root vertex, and a set of $t$ terminals. The goal is to find an orientation of the graph such that the resulting directed graph is Steiner rooted $k$-arc-connected. This problem generalizes several classical connectivity results in graph theory, such as those on edge-disjoint paths and spanning-tree packings. While the maximum $k$ for which a Steiner strongly $k$-arc-connected orientation exists can be determined in polynomial time via Nash-Williams' orientation theorem, its rooted counterpart is significantly harder: the problem is NP-hard when both $k$ and $t$ are part of the input.
In this talk, we provide a complete understanding of the problem with respect to these two parameters, thereby resolving a long-standing open problem of Király and Lau (FOCS 2006). In particular, we give an algorithm that solves the problem in time $f(k,t)\cdot n^{O(1)}$, establishing fixed-parameter tractability with respect to the number of terminals $t$ and the target connectivity $k$. We further show that the problem remains NP-hard if either $k$ or $t$ is treated as part of the input, meaning that our algorithm is essentially optimal from a parameterized perspective. By a simple reduction, our results extend beyond the Steiner setting: the same framework applies to the more general orientation problem with local connectivity requirements, establishing fixed-parameter tractability when parameterized by the total demand. Joint work with Florian Hörsch, András Imolay, and Tamás Schwarcz.
TBD
TBD