Solving shortest path with negative weights with linear program. What is the underlying problem we want to solve?

Question

Let us consider a shortest path problem with weights $w_e$ for each edge $e$. It can be formulated as a (integer) linear program (ILP). \begin{align} \min \quad &\sum_{e \in E} w_e x_e \\ s.t. \quad & A_f x_e = b_f \\ & x_e \in \{0,1\} \end{align} Here, $A_f, b_f$ are the flow conservation constraints. It is known that $A_f$ is a totally unimodular matrix so solving the relaxed version above ILP (by letting $x_e \in [0,1]$) gives us an integral solution. When the weights $w_e$ are all non-negative, the above LP is indeed a shortest path problem.

However, when $w_e$ can be negative and we allow the negative cycles in the graph, what this ILP is actually trying to solve here? I list some of my conjectures and thoughts below for your reference.

1. Longest path problem: I know that a shortest path problem with a negative cycle can be seen as the longest path problem which is NP-hard. The above ILP is certainly not NP-hard. Actually, the thing is that the above ILP allows a trail (each edge appears only once) instead of a walk (or simple path). But I am still not sure if this ILP tries to solve the shortest trail problem...
2. Min-cost flow problem: The relaxed ILP seems a special case of the min-cost flow problem with unit capacity and unit demand at the source and sink. If it is correct, is there a special name for this kind of problem?

Thanks in advance!

Answer 1

Note that the above LP allows you to have a negative weight cycle. That cycle could be edge disjoint from the flow that goes from $s$ to $t$. The cycle still satisfies the flow conservation and capacity constraints. Therefore, the solution of the above LP is not necessarily the shortest trail.

For example, consider the following graph such that each edge has capacity $1$ and weight $-1$.

The LP will assign flow $1$ to edges $(s,t)$, $(a,b)$, $(b,c)$, and $(c,a)$; and it will assign flow $0$ to the edges $(s,a)$ and $(b,t)$. Thus, the cost of the optimal solution is $-4$.

However, the shortest trail is: $s \to a \to b \to t$ of cost $-3$.