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?