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

<p>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$.  </p>

<p>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$.  </p>

<p>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.</p>

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

CC BY-SA 3.0
2012-11-22T20:41:33.997Z
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
CC BY-SA 3.0
2012-11-23T04:41:03.530Z
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
CC BY-SA 3.0
2012-11-22T02:12:31.113Z
2012-11-22T02:12:31.113Z
Neal Young
<p>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?</p>

<p>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.</p>

<ds.algorithms><graph-theory><optimization>
Splitting a graph into minimum number of subpaths
Jakub Zaverka
# Splitting a graph into minimum number of subpaths

(Asked by: username_0 on 2012-11-21)

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.

**Tags:** ds.algorithms, graph-theory, optimization

---

## 1 answers

### Answer by username_1 on 2012-11-22. Score: 11

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

> **Comments:**
> **username_0**: 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.  
> **username_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?  

---

