<p>havent heard of this problem exactly in literature [maybe someone else has] however as a "nearby problem" it seems to me the <a href="http://en.wikipedia.org/wiki/Minimum_spanning_tree" rel="nofollow">minimum spanning tree</a> would have useful properties to solve your problem. for example maybe generating two minimum spanning trees starting from the source vertex &amp; the sync vertex, and propagating them outward until they touch, etc. might solve the problem or give a close answer. before anyone dings me on this here plz understand I am extending the idea of the MST somewhat to be generated starting from a given vertex [normally it starts from shortest edge in the entire graph]. if it doesnt work Id be curious for the reason.</p>

CC BY-SA 3.0
2012-02-05T19:32:59.060Z
Sorry, but I don't see the relevance of this answer to this question.
David Eppstein
CC BY-SA 3.0
2012-02-06T01:54:27.460Z
maybe you have a better idea what he's talking about? does it make sense to you as stated?
vzn
CC BY-SA 3.0
2012-02-06T02:36:06.687Z
He needs to _assign_ weights to edges. How would calculating an MST help that?
Nicholas Mancuso
CC BY-SA 3.0
2012-02-06T17:12:57.467Z
ok on reading it, & with nobody else proposing an answer, it seemed like the problem could be converted to two parts-- (1) assign weights based on criteria/restrictions, (2) find shortest paths based on those weights. seems MST could be useful on (2). or maybe not! (eg maybe 1/2 are tightly coupled)
vzn
CC BY-SA 3.0
2012-02-14T09:13:31.773Z
No.  Minimum spanning trees are only for undirected graphs; the input graph is directed.  Moreover, minimum spanning trees are  only superficially related to shortest paths.
Jeffε
CC BY-SA 3.0
2012-02-05T19:23:51.303Z
2012-02-05T19:23:51.303Z
vzn
<p>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. </p>

<p><strong>Problem:</strong> 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.</p>

<p>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.</p>

<p><strong>Edit:</strong> Is there a hardness proof for this problem? Does the compact numbering always exists? </p>

CC BY-SA 3.0
2012-01-31T16:02:38.250Z
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
CC BY-SA 3.0
2012-01-31T16:49:13.400Z
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
CC BY-SA 3.0
2012-01-31T20:27:35.897Z
So any vertex in $R$ should act as some sort of centroid?
Nicholas Mancuso
CC BY-SA 3.0
2012-02-01T09:04:12.573Z
@NicholasMancuso i could not get you.
user5153
CC BY-SA 3.0
2012-02-01T16:27:31.317Z
I was thinking about it in terms of $R$ being a set of centroids, such that, at a higher level, any path $p$ would have an edge to a vertex $r$ with cost $c$. Given a set of paths $P$ such that they all visit some $r \in R$, $r$ would be the 'center' of $P$. That is to say,  we can view the cost of path $p$ with respect to $r$ as $p$'s total cost. Since each path $p \in P$ must be the same total cost, $r$ would be a 'center' of all these paths. Perhaps this does not totally capture the optimization problems constraints though. But it felt intuitive to me.
Nicholas Mancuso
CC BY-SA 3.0
2012-02-05T12:55:55.613Z
it is an interesting question. is it NP-Hard ? also i feel  that compact numbering may not exist in some cases.. i.e. range may not be equal to the number of paths in $P$.
singhsumit
CC BY-SA 3.0
2012-02-06T02:41:49.610Z
On second thought, trying to come up with some assignment problem over a bipartite inclusion graph will not work, as the size of the paths (right partition nodes) may not be the same. Some simple assignment in that scenario will lead to fractional weights over edges.
Nicholas Mancuso
CC BY-SA 3.0
2012-02-06T03:31:45.647Z
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
CC BY-SA 3.0
2012-02-06T07:25:24.653Z
@DavidEppstein i think one can work with vertex version of the problem with appropriate changes. Using the standard trick: We can add one new vertex $w$ for each edge $(u,v) \in E$,  such that now $(u,w),(w,v) \in E$ and the edge $(u,v)$ is removed from $E$. Now the optimal answer in edge version of the problem can be mapped to the vertex version of the problem and vice-versa. It is not clear, why giving weights to vertices in edge version of the problem (without above transformation) will give optimal range. This again will give us a upper bound though.
singhsumit
CC BY-SA 3.0
2012-02-06T17:14:53.767Z
OP you say you have an algorithm already. it might be helpful to sketch out the steps of your current algorithm which you feel succeeds on/solves the problem but with undesirable inefficiency.
vzn
CC BY-SA 3.0
2012-02-07T04:49:52.023Z
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
CC BY-SA 3.0
2012-02-07T05:59:39.917Z
@SashoNikolov your example shows that there exist examples where Eppstein's answer is almost tight but that may not hold always. e.g. consider a graph $G=(V,E)$, $V=[n] \cup \{s,t\}$ and $E=\{(s,i):i \in [n]\} \cup \{(i,t): i \in [n]\}$. Let $R=[n]$. There are now $n$ paths and path numbers are exponentially high.
singhsumit
CC BY-SA 3.0
2012-02-07T06:10:57.193Z
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
CC BY-SA 3.0
2012-02-13T08:39:24.790Z
It seems likely that if the range has weights  $o(2^|R|)$, then there exists a graph for which two paths intersected with $R$ are not the same, but still sum to the same weight.
Joe
CC BY-SA 4.0
2020-06-21T14:40:48.780Z
The objective is given as *"The range of weights of paths in $P$ should be as small as possible."*  One natural interpretation is that the "range" here is the *set* of weights of paths in $P$, i.e. $R=\{\sum_{e\in p} w(e) : p\in P\}$.  But then any solution must have the *same* range size, because the range has one element for each equivalence class of paths, where two paths are equivalent if they share the same vertices in $R$.  With this interpretation, David Eppstein's algorithm gives an optimal solution.  OP should clarify what s/he intends by "range".  Maybe $\max R$ for $R$ as above?
Neal Young
<ds.algorithms><reference-request><co.combinatorics><graph-algorithms><directed-acyclic-graph>
Exact Algorithm for edge labeling problem in DAG
user5153
# Exact Algorithm for edge labeling problem in DAG

(Asked by: username_0 on 2012-01-31)

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?

**Tags:** ds.algorithms, reference-request, co.combinatorics, graph-algorithms, directed-acyclic-graph

> **Comments:**
> **username_1**: 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?  
> **username_0**: i have edited the question. thanks for your comment. weights should be non-negative integers and the range should be as small as possible.  
> **username_2**: So any vertex in $R$ should act as some sort of centroid?  
> **username_0**: @NicholasMancuso i could not get you.  
> **username_2**: I was thinking about it in terms of $R$ being a set of centroids, such that, at a higher level, any path $p$ would have an edge to a vertex $r$ with cost $c$. Given a set of paths $P$ such that they all visit some $r \in R$, $r$ would be the 'center' of $P$. That is to say,  we can view the cost of path $p$ with respect to $r$ as $p$'s total cost. Since each path $p \in P$ must be the same total cost, $r$ would be a 'center' of all these paths. Perhaps this does not totally capture the optimization problems constraints though. But it felt intuitive to me.  
> **username_3**: it is an interesting question. is it NP-Hard ? also i feel  that compact numbering may not exist in some cases.. i.e. range may not be equal to the number of paths in $P$.  
> **username_2**: On second thought, trying to come up with some assignment problem over a bipartite inclusion graph will not work, as the size of the paths (right partition nodes) may not be the same. Some simple assignment in that scenario will lead to fractional weights over edges.  
> **username_4**: 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?  
> **username_3**: @DavidEppstein i think one can work with vertex version of the problem with appropriate changes. Using the standard trick: We can add one new vertex $w$ for each edge $(u,v) \in E$,  such that now $(u,w),(w,v) \in E$ and the edge $(u,v)$ is removed from $E$. Now the optimal answer in edge version of the problem can be mapped to the vertex version of the problem and vice-versa. It is not clear, why giving weights to vertices in edge version of the problem (without above transformation) will give optimal range. This again will give us a upper bound though.  
> **username_5**: OP you say you have an algorithm already. it might be helpful to sketch out the steps of your current algorithm which you feel succeeds on/solves the problem but with undesirable inefficiency.  
> **username_6**: 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$.  
> **username_3**: @SashoNikolov your example shows that there exist examples where Eppstein's answer is almost tight but that may not hold always. e.g. consider a graph $G=(V,E)$, $V=[n] \cup \{s,t\}$ and $E=\{(s,i):i \in [n]\} \cup \{(i,t): i \in [n]\}$. Let $R=[n]$. There are now $n$ paths and path numbers are exponentially high.  
> **username_6**: 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.  
> **username_7**: It seems likely that if the range has weights  $o(2^|R|)$, then there exists a graph for which two paths intersected with $R$ are not the same, but still sum to the same weight.  
> **username_8**: The objective is given as *"The range of weights of paths in $P$ should be as small as possible."*  One natural interpretation is that the "range" here is the *set* of weights of paths in $P$, i.e. $R=\{\sum_{e\in p} w(e) : p\in P\}$.  But then any solution must have the *same* range size, because the range has one element for each equivalence class of paths, where two paths are equivalent if they share the same vertices in $R$.  With this interpretation, username_4's algorithm gives an optimal solution.  OP should clarify what s/he intends by "range".  Maybe $\max R$ for $R$ as above?  

---

## 1 answers

### Answer by username_5 on 2012-02-05. Score: -6

havent heard of this problem exactly in literature [maybe someone else has] however as a "nearby problem" it seems to me the [minimum spanning tree](http://en.wikipedia.org/wiki/Minimum_spanning_tree) would have useful properties to solve your problem. for example maybe generating two minimum spanning trees starting from the source vertex & the sync vertex, and propagating them outward until they touch, etc. might solve the problem or give a close answer. before anyone dings me on this here plz understand I am extending the idea of the MST somewhat to be generated starting from a given vertex [normally it starts from shortest edge in the entire graph]. if it doesnt work Id be curious for the reason.

> **Comments:**
> **username_4**: Sorry, but I don't see the relevance of this answer to this question.  
> **username_5**: maybe you have a better idea what he's talking about? does it make sense to you as stated?  
> **username_2**: He needs to _assign_ weights to edges. How would calculating an MST help that?  
> **username_5**: ok on reading it, & with nobody else proposing an answer, it seemed like the problem could be converted to two parts-- (1) assign weights based on criteria/restrictions, (2) find shortest paths based on those weights. seems MST could be useful on (2). or maybe not! (eg maybe 1/2 are tightly coupled)  
> **username_9**: No.  Minimum spanning trees are only for undirected graphs; the input graph is directed.  Moreover, minimum spanning trees are  only superficially related to shortest paths.  

---

