0
$\begingroup$

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

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$ Jan 30, 2013 at 22:51
  • $\begingroup$ 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. $\endgroup$ Jan 31, 2013 at 13:20
  • $\begingroup$ 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. $\endgroup$ Jan 31, 2013 at 15:05
  • $\begingroup$ 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... $\endgroup$ Jan 31, 2013 at 15:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.