  Traffic engineering (TE) is a fundamental task in networking. Conventionally,
traffic can take any path connecting the source and destination. Emerging
technologies such as segment routing, however, use logical paths going through
a predetermined set of middlepoints. Inspired by this, in this work we
introduce the problem of node-constrained TE, where traffic must go through a
set of middlepoints, and study its theoretical fundamentals. We show that the
general node-constrained TE that constrains the traffic to take paths going
through one or more middlepoints is NP-hard for directed graphs but strongly
polynomial for undirected graphs, unveiling a profound dichotomy between the
two cases. We additionally investigate the popular variant of node-constrained
TE that uses shortest paths between middlepoints, and show that the problem can
now be solved in weakly polynomial time for a fixed number of middlepoints. Yet
if we constrain the end-to-end paths to be acyclic, the problem can become
NP-hard. This explains why existing work focuses on the computationally
tractable variant. An important application of our work concerns the
computational complexity of flow centrality, first proposed in 1991 by Freeman
et al. [21]: we show that it is NP-hard for directed but strongly polynomial
for undirected graphs. Finally, we investigate the middlepoint selection
problem in general node-constrained TE. We introduce group flow centrality as a
solution concept for multi-commodity networks, study its complexity, and show
that it is monotone but not submodular for both directed and undirected graphs.
Our work provides a thorough theoretical treatment of node-constrained TE and
its applications.
