# Maximum weight vertex-disjoint paths

I have a complete (every vertex is connected by an edge to every other vertex) undirected positively weighted graph. I want to find vertex-disjoint paths in the graph whose total weight is as large as possible.

To me this sound like a mix of the longest path problem (NP-complete) and minimum spanning tree. Finding the best solution is not required, so maybe some greedy algorithm or something would be a good fit.

Any ideas and algorithms on how to approach this problem?

• Is "a fully connected graph" just a connected graph? Extraneous modifier makes the meaning less clear. For example, "vertex-totally-disjoint paths" is less preferable if it means the same as "vertex-disjoint paths". Commented Jun 1, 2019 at 16:29
• @Apass.Jack "fully connected graph" means a graph in which each vertex is connected wit all other vertexes in the graph. A "connected" graph is one where there exists a path between every two vertexes. Commented Jun 1, 2019 at 17:08
• @Apass.Jack Sorry the correct terminology is "complete". My bad. Commented Jun 1, 2019 at 17:12
• Is maximum spanning tree without any negative edge the solution you need ? Commented Jun 1, 2019 at 20:42