15
$\begingroup$

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?

$\endgroup$
15
  • 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$ Jan 31, 2012 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, 2012 at 16:49
  • 7
    $\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$ Feb 6, 2012 at 3:31
  • 5
    $\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$ Feb 7, 2012 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$ Feb 7, 2012 at 6:10

1 Answer 1

-6
$\begingroup$

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.

$\endgroup$
5
  • 5
    $\begingroup$ Sorry, but I don't see the relevance of this answer to this question. $\endgroup$ Feb 5, 2012 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, 2012 at 1:54
  • 1
    $\begingroup$ He needs to assign weights to edges. How would calculating an MST help that? $\endgroup$ Feb 6, 2012 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, 2012 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, 2012 at 9:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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