1
$\begingroup$

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?

Improve this question
$\endgroup$
7
  • $\begingroup$ 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 $\endgroup$
    – BlueRaja - Danny Pflughoeft
    Commented Oct 8, 2019 at 16:11
  • 1
    $\begingroup$ 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 $\endgroup$
    – Yota Otachi
    Commented Oct 8, 2019 at 21:17
  • $\begingroup$ 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. $\endgroup$
    – Chandra Chekuri
    Commented Oct 8, 2019 at 21:17
  • $\begingroup$ @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. $\endgroup$
    – Mengfan Ma
    Commented Oct 9, 2019 at 1:03
  • $\begingroup$ @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. $\endgroup$
    – Chandra Chekuri
    Commented Oct 9, 2019 at 2:10

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.