3
$\begingroup$

I have a DAG, and on each edge, I have a minimum and maximum weight. I would like to assign (or determine it's impossible to assign) exact weights to each edge so that

  1. Each edge's weight is between its min and max
  2. For any two nodes $S$ and $T$ in the DAG, all paths from $S$ to $T$ have equal weight (where the weight of a path is the sum of all the weights of the edges in that path)
  3. [Bonus points] The total weight of all edges in the graph is minimized

I know I can set this up as a linear program, but that feels like overkill. There has to be a simpler way to do this. I've tried to think of a way to reduce it to a min-cost flow problem, but I've had no success so far. I think that might not be the right direction. Any ideas?

EDIT: As a starting point, for why I think this is at least tractable, here's how I would set up the linear program. Each edge is a bounded variable. To get the constraints, we can just do a breadth first search, keeping track of which edges have been traversed, to get values for each node. Arbitrarily assign the first node to value 0. When we traverse edge A, the value of the node that edge leads into is "A". An edge B coming from that node leading into a new node gets value "A + B". If we hit a node that's already been assigned a value, then we know those two values must be equal, so that becomes a constraint in the linear program. Each edge can only add at most one constraint, so the number of constraints is at most linear in the number of edges.

$\endgroup$
  • $\begingroup$ It feels like it would require a very special structure in the graph for this to even be possible. Also, there are typically exponentially many different paths to consider, so an efficient algorithm seems unlikely (unless the restricted nature of the problem means that the answer is "return 'impossible' unless some simple scheme gives a valid assignment"). $\endgroup$ – David Richerby Jun 12 at 17:40
  • $\begingroup$ I don't think the fact that there are exponentially many paths is relevant, due to transitivity. When two paths join, we know that they must have equal weight at that point, so we can throw out the history. That seems like ought to simplify things. $\endgroup$ – Paul Accisano Jun 12 at 17:47
  • $\begingroup$ "I don't think the fact that there are exponentially many paths is relevant, due to transitivity", for one, to rule out the existence of such a path. Also, when two paths converge, it does not mean their cost is equal $\endgroup$ – lox Jun 12 at 18:18
  • $\begingroup$ The number of equality constraints is $|E|-|V|+1$ for a connect DAG. We can say there is only $|V|-1$ variables. $\endgroup$ – Apass.Jack Jun 12 at 19:24
  • $\begingroup$ Since there are $|V|-1$ variables for a connect DAF, it is possible this problem is NP-hard. $\endgroup$ – Apass.Jack Jun 12 at 19:28

Your Answer

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

Browse other questions tagged or ask your own question.