On the complexity of the bilevel shortest path problem

DOI10.1002/NET.70002MaRDI QIDQ6889354zbMATH OpenFDO

Authors Dorothee Henke, Lasse Wulf

Publication date 4 December 2025

Published in Networks (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1002/NET.70002

zbMATH Keywords

bilevel optimizationcomputational complexityshortest path problem

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Games on graphs (graph-theoretic aspects) (05C57) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Programming involving graphs or networks (90C35)

Cites work

• A bilevel model of taxation and its application to optimal highway pricing
• A note on the complexity of the bilevel bottleneck assignment problem
• A note on two problems in connexion with graphs
• A study on the computational complexity of the bilevel knapsack problem
• An exact algorithm for bilevel 0-1 knapsack problems
• An Improved Algorithm for Finding Cycles Through Elements
• An overview of bilevel optimization
• An overview of Stackelberg pricing in networks
• Bilevel optimization: theory, algorithms, applications and a bibliography
• Bilevel programming and price setting problems
• Bilevel programming problems. Theory, algorithms and applications to energy networks
• Complete sets and the polynomial-time hierarchy
• Finding the most vital arcs in a network
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 475622 (Why is no real title available?)
• scientific article; zbMATH DE number 2246593 (Why is no real title available?)
• scientific article; zbMATH DE number 7053391 (Why is no real title available?)
• Inverse Optimization
• Mixed integer bilevel optimization with a k-optimal follower: a hierarchy of bounds
• New Branch-and-Bound Rules for Linear Bilevel Programming
• On bilevel minimum and bottleneck spanning tree problems
• On the complexity of robust multi-stage problems with discrete recourse
• On the complexity of the bilevel minimum spanning tree problem
• On the shortest path game
• Shortest-path network interdiction
• The computational complexity of bilevel assignment problems
• The directed subgraph homeomorphism problem
• The k most vital arcs in the shortest path problem
• The Planar Hamiltonian Circuit Problem is NP-Complete
• The polynomial hierarchy and a simple model for competitive analysis
• The polynomial-time hierarchy
• The shortest connection game
• The trouble with the second quantifier

This page was built for publication: On the complexity of the bilevel shortest path problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6889354)