1
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\begingroup$ 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". $\endgroup$
    – John L.
    Jun 1, 2019 at 16:29
  • $\begingroup$ @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. $\endgroup$
    – user103220
    Jun 1, 2019 at 17:08
  • $\begingroup$ @Apass.Jack Sorry the correct terminology is "complete". My bad. $\endgroup$
    – user103220
    Jun 1, 2019 at 17:12
  • $\begingroup$ Is maximum spanning tree without any negative edge the solution you need ? $\endgroup$
    – Optidad
    Jun 1, 2019 at 20:42

1 Answer 1

Reset to default
0
$\begingroup$

This is not NP-Complete as far as I know. Below is a way to solve it.

You can convert the problem to finding the minimal path cover of your graph by making all the weights negative. The minimal path cover is a collection of disjoint paths covering all vertices.

One way of solving this is to convert your graph into a bipartite graph by doubling the vertices and making sure every edge goes from one side to the other. You then find the maximum bipartite matching, which will give you all the edges used in the disjoint path covers, and you can then find the paths from this set.

To get the maximum bipartite matching you can convert the graph into a flow network with unit weights on edges and use Ford-Fulkerson algorithm. All edges in the max flow will be in the maximum bipartite matching. You can then stitch the edges together as there will be only one way to assemble it with minimum number of paths.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Don't you risk to get cycles when you solve the maximum bipartite matching ? $\endgroup$
    – Optidad
    Jun 1, 2019 at 20:40
  • $\begingroup$ Oh thats a good point, I didn't think of that...I just did some searching as to how to get the maximum matching of a graph, and I think Blossom Algorithm could work here en.wikipedia.org/wiki/Blossom_algorithm. I believe the idea is the same, you just don't have to convert the graph into a bipartite one you can simply run it on the original. Thanks for that catch! $\endgroup$
    – Abishek Puri
    Jun 7, 2019 at 17:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.