Edge labeling in $K_{m,n}$

Question

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?

Answer 1

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