Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

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)?

share|improve this answer
    
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. –  Jakub Zaverka Nov 22 '12 at 20:41
1  
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? –  Neal Young Nov 23 '12 at 4:41

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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