The computational complexity of continuous-discrete bilevel network problems
Elisabeth Gassner · 2009
We study a bilevel approach for combinatorial optimization problems on graphs: In our model the follower has to solve a network problem. The leader is allowed to modify parameters of the follower’s objective function and thereby influences the follower’s decision and indirectly his own outcome. The main focus of this paper is to analyse the computational complexity of such bilevel network problems. We give several conditions on the underlying network problem that imply that the associated bilevel network problem is solvable in polynomial time or NP-hard. The computational complexity of bilevel spanning tree problems is fully characterized provided that the underlying objective functions are of sum- or bottleneck-type. 1