ALOP Colloquium

As part of the colloquium of the Research Training Group Algorithmic Optimization will take place on

Monday, February 12, 2024
16:00 c.t.
Lecture hall 9

the following lecture will take place:

On the Complexity of the Bilevel Shortest Path Problem

Dorothee Henke, University of Passau

We introduce a new bilevel version of the classical shortest path problem and completely characterize its computational complexity with respect to several problem variants. In our problem, the leader and the follower each control a subset of the edges of a graph and together aim at building a path between two given vertices, while each of the two players minimizes the length of the resulting path according to their own edge lengths. We investigate both directed and undirected graphs, as well as the special case of acyclic directed graphs. Moreover, we distinguish two versions of the follower's problem: Either he has to complete the edge set selected by the leader such that the joint solution is exactly a path, without any additional edges, or he is allowed to include only a subset of the leader's selection into the final path. In general, the bilevel problem turns out to be much harder in the former case: We show that the follower's problem is already NP-hard here and the leader's problem is even hard for the second level of the polynomial hierarchy, while both problems are one level easier in the latter case. Interestingly, for acyclic directed graphs, this difference turns around, as we give a polynomial-time algorithm for the first version of the bilevel problem, but it stays NP-hard in the second case.

This is joint work with Lasse Wulf.