Using Bellman-Ford to find a Hamiltonian cycle? (NP-complete)

Question

Let $G(V,E)$ be a directed graph, where $V=\{a_1,\ldots,a_n\}$ is a set of vertices and $E$ is a set of ordered pairs of $V$, with $|V|=n$.

Now, let be $G(W,F)$ be a graph where $W$ is a set of vertices, such that $W=\{a_1,\ldots,a_{2n}\}$ with $|W|=2n$, and $F$ is a set of ordered pairs of $W$ defined as follows: $$\forall i, j \in \{1, \ldots, n\} : (a_i,a_{j+n}) \in F \text{ if } (a_i,a_{j}) \in E \\ \forall i \in \{1, \ldots, n\} : (a_{i+n},a_i) \in F$$

Now we define the capacities: $$c(a,b)=1 \text{ if } (a,b) \in F$$

And we define a cost: $$\forall i \in \{1, \ldots, n\} : p(a_{i+n},a_i)=-1 \text{ if } (a_{i+n},a_i) \in F \\ p=0 \text{ else}$$

The source as $a_{n+1}$ and the sink as $a_{n+1}$.

Does the graph $G(W,F,c,p)$ have a minimum cost flow of $-n$ if and only if the graph $G(V,E)$ has a Hamiltonian cycle?

---

(Comment to an answer in the comments section)

Michael, for your matrix with capacities G(V,E) the matrix G(W,F) is:

cap = [[0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0],
       [0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0],
       [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
       [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
       [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0]]

cost = [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [-1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0]]

Answer 1

Here is an example where the program you gave fails. This gives details from my comment above. You can plug in the following data into the Python program you linked here: https://www.geeksforgeeks.org/minimum-cost-maximum-flow-from-a-graph-using-bellman-ford-algorithm/

---

s = 6
t = 2

cap = [ [ 0, 1, 1, 1, 0, 0, 0],
        [1, 0, 1, 1, 1, 0, 0],
        [1, 1, 0, 0, 0, 0, 0],
        [1, 1, 0, 0, 1, 1, 0],
        [0, 1, 0, 1, 0, 1, 0],
        [0, 0, 0, 1, 1, 0, 1], 
        [0, 0, 0, 0, 0, 1, 0]]

cost = [ [ 0, -1, -1, -1, 0, 0, 0],
         [-1, 0, -1, -1, -1, 0, 0],
         [-1, -1, 0, 0, 0, 0, 0],
         [-1, -1, 0, 0, -1, -1, 0],
         [0, -1, 0, -1, 0, -1, 0],
         [0, 0, 0, -1, -1, 0, -1],
         [0, 0, 0, 0, 0, -1, 0]]

---

This is a graph with 7 nodes labeled {0, 1, ..., 6}. The graph is symmetric, so for every link (i,j) there is a link (j,i). All link capacities are 1 and all costs are -1. Node 6 is only connected to node 5 and so the max flow to or from node 6 is 1 unit.

I used source s=6 and destination t=2. The program gives an output of 1, -5. This means a flow of 1 unit and a cost of -5 (5 hops). This is incorrect because there is a 6-hop Hamiltonian path that the program does not find:

$$ 6\rightarrow 5\rightarrow 4 \rightarrow 3 \rightarrow 1 \rightarrow 0 \rightarrow 2 $$

On the other hand, if we reverse the path and use s=2, t=6, the program gives a correct output of 1, -6.

Unfortunately the program only outputs the cost of the path, not the actual path, so I don't know what paths it is proposing in either case.

Answer 2

No, it's possible to have a flow of cost -n without having a Hamiltonian cycle. Consider for example a graph consisting of two disjoint cycles. To make the example less trivial, you could add some edges between them without introducing a Hamiltonian cycle. The two disjoint cycles still give a flow of cost -n.

Answer 3

Let $f$ be the minimum-cost flow. That here, there [probably] are negative cost cycles does put a twist into what $f$ may look like. In particular, here is no reason why the arcs $e$ for which $f(e)$ is positive have to form a connected graph; indeed $f$ could consist of a path $P$ between $a_1$ and $a_{n+1}$ and then vertex-disjoint cycles [disjoint from $P$ as well] where each vertex participates in a cycle.

In fact you also need to require that the capacity of each vertex is also 1 and that the net flow into a vertex besides $a_1$, $a_{n+1}$ is 0; without this even edge-disjointness of the cycles suffices, and the minimum-cost flow could be less than $-n$.