# Labeling nodes in a bipartite graph to satisfy edge constraints

I'm trying to find an algorithm for the following problem. Let $$G$$ be a bipartite graph. The edges in $$G$$ have labels $$R$$; each label $$R(u, v)$$ is an integer range $$[a, b]$$ with $$a$$ and $$b$$ being nonnegative integers with $$a \le b$$. The problem is to assign each node in the graph with nonnegative integer labels $$L$$ such that

1. If $$(u, v) \in G$$ then $$L(v) - L(u) \in R(u, v)$$
2. The sum of $$L(v) - L(u)$$ for all $$(u, v) \in G$$ is minimized

Are there any similar problems that can read about to give me some insight?

• The obvious linear program may [a priori] return fractional solutions, if you round every $L(u)$ up to the nearest integer, or instead round every value of $L(u)$ down, I think that this will return a solution satisfying 1 and will change the value of the quantity as in 2. by no more than an additive $|E(G)|$. BUT, I don't know how good of an approximation ratio this is; the challenge is in instances where the sum $\sum_{uv \in E(G)} \min R(u,v)$ is small relative to $|E(G)|$; especially in instances where there are a lot of edges $uv$ such that $0 \in R(u,v)$. – Mike Apr 18 at 22:35

## 1 Answer

Thanks Mike, for some reason I hadn't thought to formulate it as a linear program. But once you do that, the answer is obvious. In fact, when you set up the linear program, the resulting matrix is totally unimodular. Which means it can be solved quite easily by any linear solver and the result will be an integer solution.