Our paper Fixed-Parameter Tractability and Hardness for Steiner Rooted and Locally Connected Orientations was accepted to FOCS 2026!
The paper studies the Steiner Rooted Orientation problem introduced by Király and Lau at FOCS 2006. Given an undirected graph, a root vertex, a set of $t$ terminals, and a connectivity requirement $k$, the goal is to orient the edges so that there are $k$ arc-disjoint directed paths from the root to every terminal. Király and Lau showed that the problem is NP-hard and asked whether it becomes polynomial-time solvable when $k$ is fixed. We give a complete parameterized complexity picture: the problem is fixed-parameter tractable when parameterized by $k+t$, but remains NP-hard for every fixed $k\geq 2$ and also for every fixed $t\geq 4$. Our algorithm extends to the more general orientation problem with local connectivity requirements, which is fixed-parameter tractable when parameterized by the total demand.