标题： 分段路由的参数化复杂性 显示英文标题

标题： Parameterized Complexity of Segment Routing

摘要： 段路由是一种近期的网络技术，通过提供对路由路径的更精细控制来优化网络吞吐量。 而不是直接从源点路由到目标点，数据包是通过中间航点进行路由的。 在连续航点之间，数据包根据传统的最短路径路由协议进行路由。 通过这种重新路由可以避免网络中的瓶颈，防止网络部分过载。 相关的NP难计算问题为段路由：给定一个具有$n$个顶点的网络，$d$个流量需求（顶点对），以及一个（小）数$k$，任务是为每个需求对找到最多$k$个航点，使得沿着这些航点的最短路径路由能够满足所有需求而不超过网络的容量。 我们研究是否可以利用现实世界通信网络的特殊结构来进行算法处理。 我们的结果包括在具有常数树宽的图上段路由问题是NP难的，即使每条需求只允许一个航点。 我们进一步排除了（在标准复杂性假设下）对于任何函数$f$和$g$，运行时间为$f(d) n^{g(k)}$的算法。 我们通过多项式时间可解的特殊情况来补充这些下界。 显示英文摘要

摘要： Segment Routing is a recent network technology that helps optimizing network throughput by providing finer control over the routing paths. Instead of routing directly from a source to a target, packets are routed via intermediate waypoints. Between consecutive waypoints, the packets are routed according to traditional shortest path routing protocols. Bottlenecks in the network can be avoided by such rerouting, preventing overloading parts of the network. The associated NP-hard computational problem is Segment Routing: Given a network on $n$ vertices, $d$ traffic demands (vertex pairs), and a (small) number $k$, the task is to find for each demand pair at most $k$ waypoints such that with shortest path routing along these waypoints, all demands are fulfilled without exceeding the capacities of the network. We investigate if special structures of real-world communication networks could be exploited algorithmically. Our results comprise NP-hardness on graphs with constant treewidth even if only one waypoint per demand is allowed. We further exclude (under standard complexity assumptions) algorithms with running time $f(d) n^{g(k)}$ for any functions $f$ and $g$. We complement these lower bounds with polynomial-time solvable special cases.