Find edge weights that fit given node weights - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T11:51:45Z http://mathoverflow.net/feeds/question/120340 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/120340/find-edge-weights-that-fit-given-node-weights Find edge weights that fit given node weights xawlaxaw 2013-01-30T17:05:41Z 2013-01-31T12:55:54Z <p>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 <em>node weights</em>. Now, I want to find symmetric, positive <em>edge weights</em> $W := [w_{ij}]_{i,j=1,...,n}$ that fit the given node weights on $G$, i.e. :</p> <ul> <li>symmetry : $w_{ij} = w_{ji}$</li> <li>positivity and $G$-restriction : $w_{ij} > 0 \Leftrightarrow (i,j) \in E$ and $w_{ij} = 0$ otherwise</li> <li>fitting the given node weights : $\forall i=1,...,n : \sum_{j=1}^n w_{ij} = d_i$</li> </ul> <p>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.</p> <p>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.</p> <p>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'.</p> <p>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?).</p> <p>So my questions are:</p> <ol> <li>feasibility: For which choices of $\mathbf{d}$ does a solution $W$ exist?</li> <li>solving: How to find an explicit solution?</li> <li>background: Can you share deeper insights regarding this topic?</li> </ol> <p>(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?)</p> http://mathoverflow.net/questions/120340/find-edge-weights-that-fit-given-node-weights/120348#120348 Answer by Günter Rote for Find edge weights that fit given node weights Günter Rote 2013-01-30T18:30:40Z 2013-01-31T12:55:54Z <p>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).</p> <p>Now, the problem for the <em>bipartite</em> 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.)</p> <p>Additional remarks.</p> <ol> <li><p>The max-flow-min-cut theorem will then lead to the following characterization:</p> <blockquote> <p>A solution exists iff there is no fractional vertex cover with cost less than $\sum d_i$.</p> </blockquote> <p>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.</p></li> <li><p>The set of feasible solutions of your system is related to the <em>perfect $b$-matching polytope</em>, 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 <em>integral</em> solutions of your system of equations.</p> <p>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.</p></li> </ol>