{"id":"arxiv:2004.08338","kind":"preprint","title":"The two player shortest path network interdiction problem","authors":["Simon Busam","Luca E. Schäfer","Stefan Ruzika"],"author_count":3,"year":2020,"published":"2020-04-17","venue":null,"cited_by":0,"doi":null,"arxiv_id":"2004.08338","nct_id":null,"source_url":"https://arxiv.org/abs/2004.08338","archive_url":"https://space-kitty.com/papers/arxiv:2004.08338","updated":"2020-08-23","pmid":null,"pmcid":null,"openalex_id":"W4327856853","pdf_url":"https://arxiv.org/pdf/2004.08338","abstract":"In this article, we study a biobjective extension of the shortest path network interdiction problem. Each arc in the network is associated with two integer length values and two players compute their respective shortest paths from source to sink independently from each other while an interdictor tries to lengthen both shortest paths by removing arcs. We show that this problem is intractable and that deciding whether a feasible interdiction strategy is efficient, is NP- complete. We provide a solution procedure to solve the problem on two-terminal series-parallel graphs in pseudopolynomial time.","abstract_license":"CC0-1.0 (arXiv descriptive metadata)","license":null,"is_open_access":false,"retracted":false,"peer_reviewed":false,"categories":["cs.DS","math.CO"],"details":null,"provenance":"arxiv","attribution":"Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.","topics":[{"slug":"algorithms-complexity","name":"Algorithms & Complexity Breakthroughs","domain_slug":"math-cs"}],"cited_in_dossiers":[]}