# Splitting a graph into minimum number of subpaths

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.

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.
• 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. Commented Nov 22, 2012 at 20:41