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?

  • 4
    $\begingroup$ 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? $\endgroup$ – Artem Kaznatcheev Jan 31 '12 at 16:02
  • 2
    $\begingroup$ i have edited the question. thanks for your comment. weights should be non-negative integers and the range should be as small as possible. $\endgroup$ – user5153 Jan 31 '12 at 16:49
  • 6
    $\begingroup$ 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? $\endgroup$ – David Eppstein Feb 6 '12 at 3:31
  • 4
    $\begingroup$ 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$. $\endgroup$ – Sasho Nikolov Feb 7 '12 at 4:49
  • 1
    $\begingroup$ 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. $\endgroup$ – Sasho Nikolov Feb 7 '12 at 6:10

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

| cite | improve this answer | |
  • 5
    $\begingroup$ Sorry, but I don't see the relevance of this answer to this question. $\endgroup$ – David Eppstein Feb 5 '12 at 19:32
  • $\begingroup$ maybe you have a better idea what he's talking about? does it make sense to you as stated? $\endgroup$ – vzn Feb 6 '12 at 1:54
  • 1
    $\begingroup$ He needs to assign weights to edges. How would calculating an MST help that? $\endgroup$ – Nicholas Mancuso Feb 6 '12 at 2:36
  • $\begingroup$ 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) $\endgroup$ – vzn Feb 6 '12 at 17:12
  • 1
    $\begingroup$ 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. $\endgroup$ – Jeffε Feb 14 '12 at 9:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.