3268. On the Complexity of the Bilevel Shortest Path Problem
Invited abstract in session TD-4: Robust and Multi-Level Optimization, stream MINLP.
Tuesday, 14:30-16:00Room: 1001 (building: 202)
Authors (first author is the speaker)
1. | Dorothee Henke
|
University of Passau | |
2. | Lasse Wulf
|
Institute of discrete mathematics, TU Graz |
Abstract
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.
Keywords
- Combinatorial Optimization
- Complexity and Approximation
- Graphs and Networks
Status: accepted
Back to the list of papers