# Find edge weights that fit given node weights

Let $G = (V,E)$ be a connected simple graph (unweighted, undirected, no selfloops) on $n$ nodes. Let $\mathbf{d} := (d_1, d_2, ..., d_n) \in \mathbb{R}_{>0}^n$ be a vector of arbitrary given node weights. Now, I want to find symmetric, positive edge weights $W := [w_{ij}]_{i,j=1,...,n}$ that fit the given node weights on $G$, i.e. :

• symmetry : $w_{ij} = w_{ji}$
• positivity and $G$-restriction : $w_{ij} > 0 \Leftrightarrow (i,j) \in E$ and $w_{ij} = 0$ otherwise
• fitting the given node weights : $\forall i=1,...,n : \sum_{j=1}^n w_{ij} = d_i$

Thus, I want to find some weighted, undirected graph $G_W$ that is constructed by assigning appropriate edge weights to the edges of $G$, which sum up to the pre-defined degrees.

Surely, there are choices of $\mathbf{d}$ for which no fitting edge weights $W$ exist, think for example of a triangle and $\mathbf{d} = (10, 1, 1)$. However, it is not hard to find non-trivial examples in which for many choices of $\mathbf{d}$ some fitting $W$ does exist.

This problem can also be interpreted as solving an underdetermined system of $n$ linear equations (one for each node) in $\frac{n^2-n}{2}$ free variables (the edge weights), plus the complicated 'positivity constraint'.

Further, one can formulate this as a linear program, which might be infeasible for some choices of $\mathbf{d}$. But I am interested in an algebraic solution (but perhaps this is already NP-complete?).

So my questions are:

1. feasibility: For which choices of $\mathbf{d}$ does a solution $W$ exist?
2. solving: How to find an explicit solution?
3. background: Can you share deeper insights regarding this topic?

(Just as a weird idea, perhaps one can define the $w_{ij}$'s as entries of some vector $\mathbf{v}$ that turns out to be an eigenvector corresponding to the maximum eigenvalue of some irreducible non-negative matrix, thus, $\mathbf{v}$ having all its entries positive by the Perron-Frobenius theorem? Perhaps feasibility corresponds to irreducibility then?)

-

You can solve it by using maximum network flow: First you duplicate every vertex $i$, creating a twin $i'$, which inherits the same degree $d_{i'}:= d_i$. Each edge $ij$ becomes two edges $i,j'$ and $i',j$. If you solve your problem on this new bipartite graph $G'$, you can recover a solution for $G$ by averaging the two copies of each edge. (and vice versa).

Now, the problem for the bipartite graph $G'$ becomes a network flow problem when you direct the edges from the $i$s to the $i'$s. The $d$s become supplies and demands. (I used this reduction in my thesis.)

1. The max-flow-min-cut theorem will then lead to the following characterization:

A solution exists iff there is no fractional vertex cover with cost less than $\sum d_i$.

A fractional vertex cover assigns a number $x_i$ to each vertex such that $x_i+x_j\ge 1$ for every edge $ij$. It is sufficient to consider values $0,\frac12,1$ for the $x$'s. (This corresponds to the dual linear program to your system of inequalities.) ADDITION: A vertex $i$ costs $x_id_i$, the total cost of a vertex cover is the sum of these quantities.

2. The set of feasible solutions of your system is related to the perfect $b$-matching polytope, see [A. Schrijver, Combinatorial Optimization, Vol. 1, p. 549]: The $b$s are your $d$s. In this problem, the $b$'s must be integral, and the perfect $b$-matching polytope is the convex hull of the integral solutions of your system of equations.

However, when all $b_i$'s are even, integrality plays no role, and you get directly the convex hull of all real solutions. This is a special section in Schrijver's book; Section 31.5. Theorem 31.5 then (if rephrased appropriately) would lead to the above characterization.

-
I see two issues here. One is that the original problem is invariant under multiplying all the $d_i$s by the same constant, but your "less than $\sum d_i$" is not. The other issue is that the OP wants the edge weights to be strictly positive, but your flow problem allows 0 flow on edges, doesn't it? –  Brendan McKay Jan 30 '13 at 22:51
1) I clarified the concept of "cost". 2) Yes I overlooked the positivity. What I said holds for the nonnegative variant. Positivity can be achieved by adding constraints $w_{ij}\ge\epsilon$ to the constraints and maximizing $\epsilon$. (After all is is a linear inequalities problem (so definitely not NP-complete)). In the network model, one can try to make a particular $w_{ij}$ positive by pushing flow around. If this works for all edges, the average of those solutions is positive on all edges. A more elegant solution identifies the arcs that have zero flow in all solutions. –  Günter Rote Jan 31 '13 at 13:20
Thanks a lot! Your reduction makes this problem much clearer, and it offers many opportunities for further theoretical and practical work on this. Currently, I focus on 'guessing' the network flow edge-wise and then use Lovasz Local Lemma to show the existence of a feasible solution for specific choices of $d$, but I still have to beat the devil in the details. –  user27164 Jan 31 '13 at 15:05
Regarding this nice polytope: I found some slides on a non-integral variant (first Google hit, titled "Fractional Perfect b-Matching Polytopes"). They also contain a proof of a necessary condition for the existence of a completely positive solution - perhaps it is possible to derive some easy to check (and not too restrictive) sufficient condition from this... –  user27164 Jan 31 '13 at 15:09