Finding the lowest cost set of disjoint paths using all nodes in a directed graph? - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-18T22:47:25Z http://mathoverflow.net/feeds/question/109893 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/109893/finding-the-lowest-cost-set-of-disjoint-paths-using-all-nodes-in-a-directed-graph Finding the lowest cost set of disjoint paths using all nodes in a directed graph? Stuart 2012-10-17T11:09:30Z 2012-10-17T16:53:50Z <p>I have a directed graph with edges connecting nodes representing costs.</p> <p>I wish to find the set of paths which -go from node 'start' to node 'end' -are node-disjoint (except for the start and end node) (i.e. each node is used once) -use all nodes in the graph -minimises the total cost (or close enough*) -all costs are positive</p> <p>In the example below, the red+green paths have the lowest cost, whilst using all nodes. The edges in blue are not used.</p> <p>see <a href="http://www.freeimagehosting.net/1lrts" rel="nofollow">http://www.freeimagehosting.net/1lrts</a></p> <p>Is there an existing algorithm to efficiently solve this problem?</p> <p>*I am aware that it is likely NP in the worst case (e.g. start-node = end-node, fully connected graph is equivalent to the Travelling salesman problem). I need an algorithm which is fast and gives good results (possibly not optimal), rather than a simple optimisation trying every combination of possibilities, which is not computationally feasible in my case.</p> http://mathoverflow.net/questions/109893/finding-the-lowest-cost-set-of-disjoint-paths-using-all-nodes-in-a-directed-graph/109894#109894 Answer by Thomas Kalinowski for Finding the lowest cost set of disjoint paths using all nodes in a directed graph? Thomas Kalinowski 2012-10-17T11:22:43Z 2012-10-17T16:53:50Z <p>I don't see the equivalence to the travelling salesman problem. I think the following works for acyclic networks:</p> <p>Split every node \$v\$ except start and end node into two copies \$v^-\$ and \$v^+\$, and add the arcs \$(v^-,v^+)\$. An arc \$(v,w)\$ of the original network is replaced by the arc \$(v^+,w^-)\$ with cost equal to the cost of \$(v,w)\$. Then your problem should be equivalent to finding a min cost flow with upper and lower capacity equal to one for the arcs of the form \$(v^-,v^+)\$. </p>