[Back]


Scientific Reports:

J. Träff:
"The Shortest Path Problem with Edge Information Reuse is NP-Complete";
Report for CoRR - Computing Research Repository; Report No. arXiv:1509.05637, 2015; 3 pages.



English abstract:
We show that the following variation of the single-source shortest path problem is NP-complete. Let a weighted, directed, acyclic graph G=(V,E,w) with source and sink vertices s and t be given. Let in addition a mapping f on E be given that associate information with the edges (e.g., a pointer), such that f(e)=f(e′) means that edges e and e′ carry the same information; for such edges it is required that w(e)=w(e′). The length of a simple st path U is the sum of the weights of the edges on U but edges with f(e)=f(e′) are counted only once. The problem is to determine a shortest such st path. We call this problem the edge information reuse shortest path problem. It is NP-complete by reduction from PARTITION.