3
$\begingroup$

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]]
$\endgroup$
16
  • $\begingroup$ Got the idea from this post stackoverflow.com/a/16770830/14870160 when thinking about finding a path between two points A,B with a third point C contained in that path (path = no repeated edges). $\endgroup$
    – yugikaiba
    Jan 2, 2021 at 17:15
  • $\begingroup$ The minimum cost flow problem has a polynomial time solution (Ford-Fulkerson or Bellman-Ford algorithm) $\endgroup$
    – yugikaiba
    Jan 2, 2021 at 17:31
  • $\begingroup$ Do you mean min cost flow of $-(n-1)$? Take a trivial example of a connected graph with only 2 nodes and 2 links, which trivially has a Hamiltonian cycle but the corresponding bipartite graph has a min cost flow of -1, if I am understanding your setup correctly. (Anton’s answer deals with the more important concept of separated cycles, explicit counter-examples there could be two completely separated 2-node graphs, so $n=4$ and a Hamiltonian cycle is impossible, yet we can still get flow weight $-3$ in its corresponding bipartite graph.) $\endgroup$
    – Michael
    Jan 2, 2021 at 19:26
  • $\begingroup$ two points (n=2) connected to each other (V), then I have 4 for W. imgur.com/a/Hdkd5oX from $x_3 \rightarrow x_1 \rightarrow x_4 \rightarrow x_2 \rightarrow x_3$ and the cost is -2. $\endgroup$
    – yugikaiba
    Jan 2, 2021 at 19:41
  • $\begingroup$ (I edited the post the source and the sink is be the same point) $\endgroup$
    – yugikaiba
    Jan 2, 2021 at 20:20

3 Answers 3

3
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ You need to do the transformation G(V,E) to G(W,F) first, try the one I wrote in the post (Too big for the comments) $\endgroup$
    – yugikaiba
    Jan 4, 2021 at 7:19
  • $\begingroup$ if you want to go from node i to node j in G(V,E) you will have to go from node i+n to node j+n in G(W,F) or (likewise) from node i to node j in G(W,F). $\endgroup$
    – yugikaiba
    Jan 4, 2021 at 7:58
  • $\begingroup$ @yugikaiba Um, no. There is no need to do the bipartite graph to find Hamiltonian paths. The graph I constructed via the cap and cost matrices shows the Python program does not work for doing what it stated (finding a max-flow with min cost). Further, I constructed the example graph so that, if the Python program did work, it would find a Hamiltonian path. If you want to do other types of transformations or examples then you are free to do it. $\endgroup$
    – Michael
    Jan 4, 2021 at 8:53
  • $\begingroup$ There is a need to do a bipartite graph and define the cost function as I did because with Bellman-Ford you can have repeated vertices (but not repeated edges). So G(W,F) by Bellman-Ford should only have a minimum cost of -n for G(W,F) if and only if G(V,E) has a hamiltonian path. $\endgroup$
    – yugikaiba
    Jan 4, 2021 at 10:17
  • $\begingroup$ It's true I forgot Bellman-Ford doesn't work when there is a negative cycle. Can't see anything that makes me think otherwise. $\endgroup$
    – yugikaiba
    Jan 4, 2021 at 17:32
3
$\begingroup$

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.

$\endgroup$
13
  • $\begingroup$ No if 2 points $a_i$, $a_j$ are disjoint in G(V,E) then either $f(a_{i+n},a_i)=0$ or $f(a_{j+n},a_j)=0$. $\endgroup$
    – yugikaiba
    Jan 2, 2021 at 17:52
  • $\begingroup$ en.wikipedia.org/wiki/Minimum-cost_flow_problem $\endgroup$
    – yugikaiba
    Jan 2, 2021 at 17:53
  • $\begingroup$ (in the sense that there is no path neither from $a_i$ to $a_j$ nor from $a_j$ to $a_i$) $\endgroup$
    – yugikaiba
    Jan 2, 2021 at 17:56
  • $\begingroup$ $\sum_{(u,v) \in F} p(u,v) f(u,v) = \sum_{i\in \{1,\ldots,n\}} -f(a_{i+n},a_i) \ge \sum_{i\in \{1,\ldots,j-1,j+1,\ldots,n\}} -f(a_{i+n},a_i) = -n+1 $ $\endgroup$
    – yugikaiba
    Jan 2, 2021 at 18:05
  • 1
    $\begingroup$ I sense you're not making the effort to understand what I write, which is frustrating. My answer produces just such a counterexample. To make it very specific, let G(V, E) be the disjoint union of two cycles, each of length 2. This obviously does not have a Hamiltonian cycle, as it is not connected. Then G(W, F, c, p) is also a disjoint union of two cycles, each of length 4, with all edges having a capacity of 1 and half the edges having a cost of -1 (the remaining having a cost of 0). The flow which gives weight 1 to all edges achieves a cost of -4, and this is clearly minimal cost. $\endgroup$ Jan 2, 2021 at 20:58
0
$\begingroup$

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$.

$\endgroup$
3
  • $\begingroup$ Give me a counter example, write down a graph G such that (don't need the picture, just the graph) G doesn't have a Hamiltonian path such that (W,F) has a minimum cost flow strictly higher than -n. $\endgroup$
    – yugikaiba
    Jan 2, 2021 at 19:52
  • $\begingroup$ I have no idea and my answer never promised such a graph--assuming each vertex has capacity 1 that is. However, $G$ can be a bunch of vertex-disjoint cycles and the flow will have value $-n$; it just won't form a connected subgraph. $\endgroup$
    – Mike
    Jan 2, 2021 at 19:58
  • $\begingroup$ if you a graph G(V,E) with just two disconnected points with no edges $x_1$ and $x_2$ then you just can't find a minimum cost flow from $x_3 $ to $x_3$ for G(W,F) with a cost of -2 (indeed the cost will be as low as the largest subcycle in G(V,E) that goes through x_1, in this example imgur.com/a/KfANro6 zero) $\endgroup$
    – yugikaiba
    Jan 2, 2021 at 20:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .