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

Preprint · Jesper Larsson Träff

- Archive id: arxiv:1509.05637
- Published: 2015-09-18
- arXiv: https://arxiv.org/abs/1509.05637
- Source URL: https://arxiv.org/abs/1509.05637
- PDF: https://arxiv.org/pdf/1509.05637
- Provenance: arxiv

## 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')$ 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 \\emph{edge information reuse shortest path problem}. It is NP-complete by reduction from 3SAT.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.