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