Complexity of Inverse Shortest Path Routing
2011 (English)In: Network Optimization: 5th International Conference, INOC 2011 / [ed] J. Pahl, T. Reiners, and S. Voß, Springer Berlin/Heidelberg, 2011, 339-353 p.Chapter in book (Refereed)
The inverse shortest path routing problem is to decide if a set of tentative routing patterns is simultaneously realizable. A routing pattern is defined by its destination and two arc subsets of required shortest path arcs and prohibited non-shortest path arcs. A set of tentative routing patterns is simultaneously realizable if there is a cost vector such that for all routing patterns it holds that all shortest path arcs are in some shortest path and no non-shortest path arc is in any shortest path to the destination of the routing pattern. Our main result is that this problem is NP-complete, contrary to what has been claimed earlier in the literature. Inverse shortest path routing problems naturally arise as a subproblem in bilevel programs where the lower level consists of shortest path problems. Prominent applications that fit into this framework include traffic engineering in IP networks using OSPF or IS-IS and in Stackelberg network pricing games. In this paper we focus on the common subproblem that arises if the bilevel program is linearized and solved by branch-and-cut. Then, it must repeatedly be decided if a set of tentative routing patterns is realizable. In particular, an NP-completeness proof for this problem is given.
Place, publisher, year, edition, pages
Springer Berlin/Heidelberg, 2011. 339-353 p.
Lecture Notes in Computer Science, ISSN 0302-9743 (print), 1611-3349 (online) ; 6701
IdentifiersURN: urn:nbn:se:liu:diva-73152DOI: 10.1007/978-3-642-21527-8_39ISBN: 978-3-642-21526-1 (print)ISBN: 978-3-642-21527-8 (online)OAI: oai:DiVA.org:liu-73152DiVA: diva2:467470