Finding the Minimum-Weight k-Path

Avinatan Hassidim, Orgad Keller, Moshe Lewenstein +1

Given a weighted $n$-vertex graph $G$ with integer edge-weights taken from a range $[-M,M]$, we show that the minimum-weight simple path visiting $k$ vertices can be found in time…