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



Find edge weights that fit given node weights
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.


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.


