[Math] positive weighted directed graphs

graph theory

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?

Best Answer

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.

Related Question