# Exact Algorithm for edge labeling problem in DAG

I am implementing some system part of which requires some help. I am therefore framing it as a graph problem to make it domain independent.

Problem: We are given directed acyclic graph $G=(V,E)$. Without loss of generality assume that $G$ has exactly one source vertex $s$ and exactly one sink vertex $t$; let $P$ denote the set of all directed paths from $s$ to $t$ in $G$. We are also given a set of vertices $R \subseteq V$. The problem is to assign non-negative integer weights to the edges of $G$, so any two paths in $P$ have the same weight if and only if they contain the same subset of vertices in $R$. (The weight of a path is the sum of the weights of its edges.) The range of weights of paths in $P$ should be as small as possible.

Currently my approach does not seems efficient; I am just looking for some references to literature or some good insights. Anything otherwise is also appreciated.

Edit: Is there a hardness proof for this problem? Does the compact numbering always exists?

• please clarify "The range of weights of paths in P should be optimal." Are weights only integers? Are we allowed negative weights? Does optimal mean "as small a range as possible" or does it mean something else? – Artem Kaznatcheev Jan 31 '12 at 16:02
• i have edited the question. thanks for your comment. weights should be non-negative integers and the range should be as small as possible. – user5153 Jan 31 '12 at 16:49
• A simple strategy for coming up with a valid solution would be to assign a different power of two to each vertex v in R, use that number as the weight of all incoming edges to v, and assign weight zero to all remaining edges. Obviously, this might not be optimal, but it at least gives an upper bound on the range needed. Is it ever an improvement to make different edges through the same vertex in R have different weights from each other, or can you simplify the problem by making the weights go with vertices rather than edges? – David Eppstein Feb 6 '12 at 3:31
• BTW @DavidEppstein's answer shows that the max total weight of a path is $O(2^{|R|})$. This is tight up to constants. As an example, you can take the graph $G = (V, E)$, $V = [n] \cup \{s, t\}$ and $E = \{(i, j): i<j\} \cup \{(s, 1), (n, t), (s, t)\}$. Let also $R = [n]$. There are $2^n$ different paths on $R$, and since each path has non-negative integer weight, at least one needs to have weight at least $2^n -1$. – Sasho Nikolov Feb 7 '12 at 4:49
• sure, i meant tight in the worst case (i actually wrote that in the first version of this comment which got lost). thought it would be good to first pin down some absolute bounds, since no one has tackled the optimization problem yet. – Sasho Nikolov Feb 7 '12 at 6:10