Background: I have been working on the following problem and was curious if this has come up before, what is it called in the literature, and what are previously tried methods? The motivation for working on this is involved with a certain sequence assembly problem I am working with in bioinformatics.

Problem: Given a complete bipartite graph $G = (A, B, E)$ and positive integer weights, label edges (with non-negative integers) such that,

$\sum_j w_{ij} = w_i$

That is, for each vertex $i$, label incident edges such that their sum is equivalent to $w_i$.

Does a given instance have a solution? (Sketch) Split each vertex $i$ with weight $w_i$ into $w_i$ copies of weight 1. So long as a perfect matching exists, we can solve the above equation.

How to solve? Since the rank of bipartite graphs is $n - 1$ we can see that there exists a solution with at most $n - 1$ edges that will receive non-negative labels.

A simple greedy algorithm can produce a solution by simply matching the maximum vertices, labeling the edge as the min of the two, reducing the counts, and continuing on the remaining vertices.

But these solutions assume that the sums of the weights in $A$ and $B$ are equivalent. So how can we generalize when the weights are uneven? And furthermore, what if we want to maximize the number of 0 labelings?

Generalized Approach: If we set weights in $A$ to positive values and weights in $B$ to negative values we may solve with a dynamic programming solution to minimize the absolute value of the sum of each connected component.

$\text{MinForest}(S, v) = \begin{cases} \infty \text{ if } v \text{ is not valid in } S \\ w(v) + min_{S’ = \text{ partitions of S with respect to r}} \text{MinForest}(S’ - \{r\}, i) \forall i \in S & \text{ otherwise} \end{cases}$

where a vertex $v$ is valid iff $w(v) + \sum_{u \in \text{children}} w(u)$ is between 0 and $w(v)$. Any unlabeled edge will be assigned a value of 0.

Alternatives? Now it appears similar to edge-graceful labelings, but without the modulo requirement. Are there other edge labeling problems similar to this? Additionally, do these current approaches seem sound?

  • $\begingroup$ What problem are you actually trying to solve? When you ask for a generalization to unequal weight-sums, is there any feature would you hope to optimize, apart from minimizing the number of non-zero weights? Is there a particular reason you switch to considering A to have positive vertex-weights, and B negative weights? $\endgroup$ – Niel de Beaudrap Feb 7 '12 at 19:43
  • $\begingroup$ We make the assumption of assigning one side positive and the other negative w.l.o.g as it just simplifies summing the total weights. $\endgroup$ – Nicholas Mancuso Feb 7 '12 at 19:52

Not sure if I understand your problem correctly, but how about considering it as a flow network problem:

  1. Consider all edges between $A$ and $B$ to be directed edges from $A$ to $B$, the capacity of such edges will be infinity.
  2. Add a source $s$ from which an edge goes out to each of the vertices in A. The capacity of an edge $(s, a_i)$ where $a_i \in A$ is $w(a_i)$.
  3. Add sink $t$, and from every $b_j \in B$ an edge $(b_j,t)$ with capacity $w(b_j)$.

A maximum flow algorithm will assign weights to the edges between A and B, and you're done (the common algorithms also guarantee that the weights are integers).

  • $\begingroup$ That definitely is an approach that works reasonably well. One of my colleagues tried that several years ago for a similar assembly problem with slightly different constraints. $\endgroup$ – Nicholas Mancuso Feb 8 '12 at 16:11
  • $\begingroup$ Why doesn't it solve your problem? $\endgroup$ – Shir Feb 8 '12 at 17:58
  • $\begingroup$ I realized its not the best model for regular flows. If I use multi-commodity unsplitable flows, then I can more accurately describe the data. Thank you for your response. $\endgroup$ – Nicholas Mancuso Feb 9 '12 at 16:04

Your Answer

