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
- Each edge's weight is between its min and max
- 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)
- [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.