1
$\begingroup$

I need to construct a graph with the following properties:

  1. $w(u, v)$ = $-w(v, u)$, for every edge $(u, v) \in E$
  2. Weight of all $u \leadsto v$ paths is equal, for every $u, v \in V$ (this is zero weight cycle property from the title).
  3. Weight of $s \leadsto t$ paths is maximal, for some input vertices $s$ and $t$

Yes, this originates from a flow problem.

And I know an algorithm that performs such construction. Let $d(u)$ denote $|s \leadsto u|$, the length of every path from $s$ to $u$.

Initialization:

Let $d(s) \leftarrow 0$, $d(t) \leftarrow 1$ and $d(v) \leftarrow$ some real value from $[0, 1)$, for every other vertex.

Advance:

ITERATIONS ← some big value

perform ITERATIONs times: 
  new_d ← array for zeros

  for ( vertex v in V )  # visit order is arbitrary
    sum ← 0
    for ( every edge (v, u) )
      sum ← sum + d[u]     
    d[v] ← sum / degree[v]    # d[v] is an Arithmetic mean.

  d ← new_d
  d[s] ← 0
  d[t] ← 1
end

That's it. Weight of edge $(u, v)$ is equal to $d(u) - d(v)$. I mentioned maximization of $s \leadsto t$ paths, and they are indeed maximal, as $d(v) < 1$ for every $v \neq t$. Weight can now scaled.

An example of algorithm output: enter image description here

$0.384 = \frac{(0.461 + 0.539 + 0.154)}{3}$ and $0.154 = \frac{(0 + 0 + 2.30 + 3.84)}{4}$ I didn't draw inverse edges for convenience.

I don't know why this algorithm works as I don't get why arithmetic mean should be picked. Could anyone explain the sequence of thought one could get to arrive at the idea that distance to vertex should be an arithmetic mean of neighbour distances for the graph to satisfy second property?

$\endgroup$
  • $\begingroup$ Presumably, a fixed point of this procedure – where every weight is equal to the arithmetic mean of neighbor distances – satisfies the zero weight cycle property. $\endgroup$ – Yuval Filmus Apr 28 '18 at 11:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.