4
$\begingroup$

Consider a directed graph with real-number weights on the edges. I'll call the graph "positive" if the sum of weights along every circuit is positive. (It's easy to check for positivity: just make sure the circuit sum is positive for all circuits that don't pass through the same vertex twice.)

Given a directed graph, call two weightings "equivalent" if they produce the same sums on circuits.

Given a weighting, it's easy to produce an equivalent one: choose a vertex, choose a real number m, then add m to each incoming edge weight and subtract m from each outgoing edge weight.

Question #1: is the set of equivalent weightings generated by that operation?

Question #2: given a positive directed graph, does there always exist an equivalent weighting in which each edge weight is positive?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

I assume that when you say the weight of any circuit is positive, you mean that for every directed cycle $C$, $\sum_{e \in E(C)} w(e) > 0$. There's a similar model of group labeled graphs where you calculate the weight of a circuit by either adding or subtracting $w(e)$ depending on whether you traverse the edge according to the direction or not.

The answer to 2. is "yes" if we assume the graph has every edge contained in a cycle. First, observe that it suffices to prove it for rational weights - just subtract a tiny epsilon from each edge to make it's weight rational without altering the fact that each cycle has positive weight.

Your operation for finding an equivalent weight function on the edges can be generalized: if we take any edge cut $\delta(U)$ for a subset $U \subseteq V(G)$ and a value $m \in \mathbb{R}$, then if we add $m$ to all the edges of $\delta^{in}(U)$ and subtract $m$ from $\delta^{out}(U)$, we won't change the weight of any cycle. Call this operation $resigning~on~a~cut$. (In fact, resigning on a cut $\delta(U)$ for a subset of vertices $U$ is the same as repeatedly resigning by the same value on each of vertices in $U$). Say two weight functions are $flip~equivalent$ if one can be obtained from the other by repeatedly re-signing on a cut.

A weight function is $non-negative$ if the weight of any cycle is not negative. We claim that if $G$ has the property that every edge is contained in a cycle, then any non-negative rational weight function is flip equivalent to one where every edge has non-negative weight. Assume the claim is false. It suffices to prove the claim for integer weight functions by re-scaling. Pick a counterexample on a minimal number of vertices, and subject to that, to minimize $\sum_{e \in E(G): w(e) \ge 0} w(e)$. If there exists a cycle $C$ such that $w(C) = 0$, then there exists a weight function $\bar{w}$ which is flip-equivalent to $w$ such that $\bar{w}(e) = 0$ for all edges $e \in E(C )$. To see this, number the edges of $C$ $e_1, \dots, e_k$ so that they occur in that order on $C$. We can force $e_i$ for $1 \le i \le k-1$ to have weight 0 by sequentially resigning on $\delta(v_{i+1})$. After doing so, the weight on $e_k$ will be the weight of the cycle, namely 0.

Consider the graph $G'$ obtained by contracting the cycle $C$ to a single vertex and deleting any loops which arise. Note that this preserves the property that every edge is contained in a cycle, and it also holds that each loop must have positive weight in $\bar{w}$. Let $w'$ be the weight function obtained by restricting $\bar{w}$ to the edges of $G'$. Then $G'$ has no negative weight circuit, since any such circuit could be rerouted through $C$ to give a negative weight cycle in $G$. Thus, $w'$ on $G'$ can be made non-negative by repeatedly resigning on cuts. Since each cut of $G'$ is a cut of $G$ as well, it follows that $\bar{w}$ can be made non-negative by repeatedly resigning on cuts.

Thus, we may assume that every cycle has strictly positive weight, and consequently, weight at least 1. It follows that there must exist an edge $f$ with $w(f) \ge 1$. Fix such an edge $f$, and let $w''$ be the weight function with $w''(e) = w(e)$ for all $e \neq f$ and let $w''(f) = w(f) - 1$. By construction, $w''$ is a non-negative since the weight of any cycle decreases by at most $1$. Moreover, $\sum_{e \in E(G): w''(e) \ge 0} w''(e)$ has strictly decreased, so by our choice of counterexample, there exists a weight function which is flip equivalent to $w''$ where every edge has non-negative weight. By resigning on the same series of cuts, we find a weight function which is flip equivalent to $w$ where every edge has non-negative weight, contradicting our choice of counterexample.

Now to see that the same result holds for rational weight functions where every cycle has strictly positive weight, let $z$ be such a weight function. By above there exists a weight function $z'$ which is flip-equivalent to $z$ such that every edge has $z'(e) \ge 0$. Pick such a $z'$ to have has few edges of weight zero as possible. The function $z'$ does not have any cycles where every edge has weight 0 in $z'$. Thus, if there are any edges $z'(e) = 0$, it follows that there is a vertex $v$ such that $v$ has some out edge of weight zero and no in edge of weight zero. If we let $\epsilon= min_{e \in \delta(v)} z'(e)$, then adding $\epsilon/2$ to each of the out edges of $v$ and subtracting $\epsilon/2$ from all the in edges will maintain the property of being a non-negative weighting and strictly decrease the number of edges of weight zero, a contradiction.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Great - glad it works. If you need the result for general graphs (i.e. not strongly connected), the proof can be extended. If there is a directed cut, inductively re-sign both halves of the cut. Performing the same operations on the original graph will leave every edge positive, except for possibly edges of the cut we decomposed on. But since it is a directed cut, we can add some arbitrarily large number to every edge of the cut and the resulting graph has every edge with positive weight. $\endgroup$
    – Paul Wollan
    Commented Mar 9, 2012 at 23:36
  • $\begingroup$ Slightly simpler proof (based heavily on yours): suppose every edge is in a cycle and the weight function is nonnegative (positive). Choose cycle with minimal weight w and n vertices, n>1, with no vertex repeated. In the usual way transform the cycle so each edge has weight w/n. Claims: 1) every edge beginning and ending at vertices in the cycle is nonnegative (positive). 2) if you contract the cycle to a point, the weight function on the resulting graph is nonnegative (positive). 3) any valid transformation of the contracted graph can be done on the corresponding edges of the original graph. $\endgroup$
    – David Hillman
    Commented Mar 17, 2012 at 18:27
  • $\begingroup$ Proof of (1): consider $e: u\to v$ having weight $z$. If $u=v$ then $e$ determines a cycle so done. If not, there is a path in the cycle containing $k$ edges having weight $kw/n$ with $k>0$, and $z>=kw/n$ or else that cycle didn't have minimum weight. Done. $\endgroup$
    – David Hillman
    Commented Mar 17, 2012 at 18:39
  • $\begingroup$ Proof of (2): consider cycle $c$ in contracted graph with weight $z$. If $c$ doesn't contain contracted vertex, clearly $z$ is nonnegative (positive). Otherwise $z$ is the weight of a path $p:u\to v$ in the original graph with $u$ and $v$ in the original cycle. Now use argument of (1) with $e$ replaced by $p$. $\endgroup$
    – David Hillman
    Commented Mar 17, 2012 at 19:00
  • $\begingroup$ Proof of (3): if $v$ is the contracted vertex and $f$ is a vertex function on the contracted graph, let $g$ be a vertex function on the original graph which is the same as $f$ for corresponding vertices not in the cycle and which assigns $f(v)$ to each vertex in the cycle. This does the trick (the gradient of $g$ gives the same values as the gradient of $f$ on corresponding uncontracted edges and gives zero on all contracted edges). $\endgroup$
    – David Hillman
    Commented Mar 17, 2012 at 19:02
3
$\begingroup$

The set of weightings whose sum vanishes along each cycle corresponds exactly to gradients of functions on vertices (in other words, the weight of an edge is $f(h) - f(t),$ where $h, t$ are head and tail respectively. This is easy to show. I assume this is equivalent to what you are suggesting for Question 1. For Question 2, I am quite sure that the answer is NO, and there is a very round-about geometric way of seeing it (basically, conditions on cycle sums of exterior dihedral angles together with positivity gives a necessary and sufficient conditions for a realization of a polyhedron as a convex ideal polyhedron, and some combinatorial types are not so realizable, but can be realized as non-convex ideal polyhedra, which means that you can't keep the cycle sums the same while making the edge weights positive. A complete explanation is too long, but you can check out my papers (sorry for the self-promotion, but these are the ones I know best :)):

For Q1: Arxiv preprint "Walks on free groups and other stories". For Q2: "On the geometry of convex ideal polyhedra in hyperbolic 3 space" (Annals of Math '94) and "Combinatorial optimization in geometry" (advances in applied math, 2002(?), there is also an arxiv version.

I am sure there is a much simpler way to construct a counterexample to Q2, but nothing leaps to mind.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ @Igor: You must have some extra conditions in mind for Q1. Consider an acyclic digraph. $\endgroup$
    – Brendan McKay
    Commented Mar 5, 2012 at 2:16
  • $\begingroup$ @Brendan: I think I am thinking of a somewhat different setting than the one in the question... Hmm... $\endgroup$
    – Igor Rivin
    Commented Mar 5, 2012 at 13:15
  • $\begingroup$ The gradient thing is equivalent to what I was saying. Clearly it fails (e.g. consider a graph with two vertices and two parallel edges between them: we should be able to make the weights arbitrary, but can't). $\endgroup$
    – David Hillman
    Commented Mar 5, 2012 at 21:29
  • $\begingroup$ I think the condition that makes it work is that the graph is strongly connected. Construct outgoing and incoming spanning trees with root at $v$. Let $p_w$ be path from $v$ to $w$ on outgoing tree and $q_w$ be path from $w$ to $v$ on incoming tree. Zero edges on outgoing tree by subtracting the gradient where $f(w)$ is the sum of weights on $p_w$. Then the weight on edge $e:w\to x$ is the sum of weights on circuit $p_w e q_x$ minus the sum of weights on circuit $p_x q_x$. So this is a canonical form achieved by the desired moves. $\endgroup$
    – David Hillman
    Commented Mar 5, 2012 at 21:38
  • $\begingroup$ @David: Right, and to take this a tiny bit further, a characterization of when Q1 has answer "yes" is that the digraph is a disjoint union of strongly connected digraphs (which is equivalent to every edge lies on a cycle). $\endgroup$
    – Brendan McKay
    Commented Mar 6, 2012 at 13:09

You must log in to answer this question.

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