In the last years, many techniques have been proposed to improve the traffic engineering in telecommunication networks, among which Segment Routing (SR) attracted much attention. SR allows one or more waypoints, or so called segments, to be applied on the packet, which needs to be visited in order before being sent to the destination. Waypoints makes large-scale steering of individual packets possible, and allows more sophisticated control over the traffic. However, how to efficiently compute the segment list to minimize the maximum link utilization (MLU) is one of the most popular and the most important problems.

The computational cost of solving this problem is high due to the very large search space. We focus here on how to select a subset of the nodes using Tree Decomposition (TD) rather than making every node a waypoint candidate. We also provide a local search algorithm to validate this approach. Preliminary experimental results show that the tree decomposition provides a smaller search space for the problem, speeding up the algorithm while maintaining the high quality of the solution.