Characterizing Demand Graphs for (Fixed-Parameter) Shallow-Light Steiner Network

Abstract

We consider the Shallow-Light Steiner Network problem from a fixed-parameter perspective. Given a graph $G$, a distance bound $L$, and $p$ pairs of vertices $(s_1,t_1),\cdots ,(s_p,t_p)$, the objective is to find a minimum-cost subgraph $G^{\prime }$ such that $s_i$ and $t_i$ have distance at most $L$ in $G^{\prime }$ (for every $i\in [p]$). Our main result is on the fixed-parameter tractability of this problem with parameter $p$. We exactly characterize the demand structures that make the problem "easy", and give FPT algorithms for those cases. In all other cases, we show that the problem is W$[1]$-hard. We also extend our results to handle general edge lengths and costs, precisely characterizing which demands allow for good FPT approximation algorithms and which demands remain W$[1]$-hard even to approximate.