5
$\begingroup$

I have an ordinary weighted graph. I need to traverse every edge in the graph at least once. BUT I must do it in subpaths of maximum length L. Those subpaths need not be connected to each other. There is no edge greater than L. How to find out the minimum number of paths neccessary and how to find out these paths?

First I thought about Chinese Postman, but it gives one big path, which might not be the optimal solution. I also thought about bin packing problem, but I am not sure how to ensure the edges in every "bin" form a path.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
11
$\begingroup$

Your problem (as stated) seems to be NP-hard. Here is a reduction from Partition.

Given an instance of Partition (a collection $x_1,\ldots,x_n$ of positive integers), construct a graph with $n+1$ vertices $v_1,\ldots,v_{n+1}$ and, for each $i$, two edges from $v_i$ to $v_{i+1}$: one of cost zero, one of cost $x_i$.

Suppose the Partition instance is satisfiable. That is, there is a subset $S$ of $[n]$ such that $\sum_{i\in S} x_i = \sum_{i} x_i/2$. Then there are two paths that together cover all the edges, with each path costing $L=\sum_{i} x_i/2$.

Conversely, if there are two paths each of cost at most $L$ (that cover all the edges), the two paths together must cover each $x_i$ exactly once, and the total weight on each must be exactly $L$. So there must be a subset $S$ such that $\sum_{i\in S} x_i = \sum_i x_i/2$. That is, the Partition instance is satisfiable.

Perhaps you have further restrictions (e.g. polynomially bounded integer edge weights)?

Improve this answer
$\endgroup$
2
  • $\begingroup$ In my concrete example, both $L$ and edge weights are polynomially bounded, let's say 100. Edge weights are rational numbers (they come from a series of measurements). The size of the graph is unbounded, but the restriction that each path cannot be longer than $L$ still applies. $\endgroup$
    – Jakub Zaverka
    Nov 22, 2012 at 20:41
  • 1
    $\begingroup$ You say the weights (and L) are rational and polynomially bounded.. but that combination isn't really a restriction (we could take arbitrary integer weights, divide by the max, and get weights bounded by 1, so the above reduction would still show NP-hardness). Can we assume the weights are integers and bounded? Or maybe just the ratio between the largest and smallest weight is bounded? $\endgroup$
    – Neal Young
    Nov 23, 2012 at 4:41

Your Answer

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

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