Parameterized Complexity of Segment Routing

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 and a set of traffic demands (vertex pairs), the task is to find for each demand pair the placement of a given number of 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) the existence of efficient exact algorithms even if we assume a fixed number of waypoints per demand and a “small” amount of traffic demands. We complement these lower bounds with polynomial-time solvable special cases.