The Shortest Path Problem with Edge Information Reuse is NP-Complete

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 associates information with the edges (e.g., a pointer), such that $f(e)=f(e^{\prime })$ means that edges $e$ and $e^{\prime }$ carry the same information; for such edges it is required that $w(e)=w(e^{\prime })$. 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^{\prime })$ are counted only once. The problem is to determine a shortest such $st$ path. We call this problem the \emph{edge information reuse shortest path problem}. It is NP-complete by reduction from 3SAT.