Find edge weights that fit given node weights

2013-01-30T17:05:41Z

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:

feasibility: For which choices of $\mathbf{d}$ does a solution $W$ exist?
solving: How to find an explicit solution?
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?)

Answer by Günter Rote for Find edge weights that fit given node weights

2013-01-30T18:30:40Z

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

Additional remarks.

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

Find edge weights that fit given node weights - MathOverflow

Find edge weights that fit given node weights

Answer by Günter Rote for Find edge weights that fit given node weights