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

CC BY-SA 4.0
2019-10-08T17:36:05.867Z
2019-10-08T17:36:05.867Z
Laakeri
<p>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.</p>

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

<p>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?</p>

CC BY-SA 4.0
2019-10-08T16:11:24.833Z
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](https://cstheory.stackexchange.com/questions/17462) should work
BlueRaja - Danny Pflughoeft
CC BY-SA 4.0
2019-10-08T21:17:40.317Z
I think what you are talking about are "trails", not "trials". With the right word, you can find the answer on this site. See https://cstheory.stackexchange.com/questions/20682/
Yota Otachi
CC BY-SA 4.0
2019-10-08T21:17:45.840Z
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
CC BY-SA 4.0
2019-10-09T01:03:07.400Z
@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
CC BY-SA 4.0
2019-10-09T02:10:16.583Z
@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
CC BY-SA 4.0
2019-10-09T02:30:40.350Z
@ChandraChekuri Suppose there is no Hamilton Cycle in $G$ but we can vistit all vertices in $G'$ via a trail, then I couldn't figure out why more unit weight edges would be include. There can be a small cycle in the trail, and the cost would still be n-2nW.
Mengfan Ma
CC BY-SA 4.0
2019-10-23T13:04:58.440Z
in an undirected graph, this problem is in P: you compute a minimum {s,t}-join.
Mathieu Mari
<graph-theory><np-hardness><shortest-path>
Find the shortest s-t trail(edge disjoint path) in a graph with negative weight edges
Mengfan Ma
# Find the shortest s-t trail(edge disjoint path) in a graph with negative weight edges

(Asked by: username_0 on 2019-10-08)

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?

**Tags:** graph-theory, np-hardness, shortest-path

> **Comments:**
> **username_1**: 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](https://cstheory.stackexchange.com/questions/17462) should work  
> **username_2**: I think what you are talking about are "trails", not "trials". With the right word, you can find the answer on this site. See https://cstheory.stackexchange.com/questions/20682/  
> **username_3**: 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.  
> **username_0**: @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.  
> **username_3**: @username_0 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.  
> **username_0**: @ChandraChekuri Suppose there is no Hamilton Cycle in $G$ but we can vistit all vertices in $G'$ via a trail, then I couldn't figure out why more unit weight edges would be include. There can be a small cycle in the trail, and the cost would still be n-2nW.  
> **username_4**: in an undirected graph, this problem is in P: you compute a minimum {s,t}-join.  

---

## 1 answers

### Answer by username_5 on 2019-10-08. Score: 4 | Accepted answer

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.


---

