# Find the shortest s-t trail(edge disjoint path) in a graph with negative weight edges

A walk in a graph is a finite or infinite sequence of edges which joins a sequence of vertices. A trail is a walk in which all edges are distinct. Note that a trial may visit a vertex multiple times as long as no edge is revisited.

Given a directed graph $$G=(V,E)$$ where the weight of each edge may be negative. Let $$s,t \in V$$ be our source and destination vertices, respectively. We are asked to find the shortest $$s-t$$ trail in $$G$$.

This problem seems harder than the elementary shortest path problem. But I failed to reduce it to this problem. I've also tried to do reductions from Hamiltonian cycle or feedback arc set, however I failed again. Could you please shed some light upon it?

• Is the "longest edge-disjoint path" problem knowing to be NP-hard? If so, the same logic as the "shortest vertex-disjoint path with negative cycles" problem should work – BlueRaja - Danny Pflughoeft Oct 8 '19 at 16:11
• I think what you are talking about are "trails", not "trials". With the right word, you can find the answer on this site. See cstheory.stackexchange.com/questions/20682 – Yota Otachi Oct 8 '19 at 21:17
• Can't you reduce Hamiltonian Path/Cycle? Take an unweighted graph $G$ and to each vertex $v$ add a dummy vertex $v'$ connected only to $v$ via large negative length edges in both directions. – Chandra Chekuri Oct 8 '19 at 21:17
• @ChandraChekuri A vertex in $G$ can be revisited via a cycle containing it. So even if $G$ has no Hamiltonian cycle, we can visit all vertices in $G'$ by a trail, thus visiting all dummy cycles. – Mengfan Ma Oct 9 '19 at 1:03
• @Mengfan Ma Yes, that is true but if there is a Hamitonian cycle the cost would be n - 2nW where W is the weight of the dummy edges. If there is no Hamilton Cycle it will necessarily have include more unit weight edges of the original graph. – Chandra Chekuri Oct 9 '19 at 2:10

The longest path problem can be reduced to this problem. Let $$G = (V,E)$$ be an instance of longest $$s,t$$-path problem. For each vertex $$v \in V$$ create two vertices, $$v_{in}$$ and $$v_{out}$$, and a directed edge with weight $$-1$$ from $$v_{in}$$ to $$v_{out}$$. For each edge $$(u, v) \in E$$, create an edge from $$u_{out}$$ to $$v_{in}$$ with weight $$0$$. Now each trial in this graph corresponds to a simple path in the graph $$G$$, and the edges with weight $$-1$$ count its length.