# Find two non overlapping paths in undirected graph I’ve been struggling on how to approach a problem for over two weeks now. I am supposed to generate an undirected graph which represents a map of streets, and I am supposed to divide the map into two sets of non overlapping streets and both paths should be roughly the same distance.

Is this a common CS problem? What kind of algorithm should I use to solve it?

I’m just looking for a general direction here on what kind of algorithm should I use to do that. I’m a self taught newbie in CS and maths so I have some major gaps in my formal knowledge. The thing is, that I’m supposed to show that the technique I use to solve it involves AI. Initially I tought that I could ask this question aiming to solve the problem straight from the graph. But I now realize that my lack of technical knowledge prevented anyone from clearly understanding the problem.

Anyway, I thought of solving the problem by what I think is the Hungarian Algorithm to solve the Travelling Salesman Problem as shown here. I expected to obtain the most optimum path to traverse the whole graph and after that walk such path and stopping in the edge closest to half the total distance in order to have the two paths I required. However, not sure if it will work and I’m probably going in a completely wrong direction here. Thanks in advance. Posted on Categories proxies