Finding best paths in a fully connected graph

Question

I have a fully connected graph (undirected) with 500 vertices. This results in a matrix with 250,000 entries (only 125,000 are necessary because its undirected).

Each edge has a specific weight. If I can only visit n vertices where n < 500 is it possible to find which starting vertex and which path would result in the highest total weights.

Is this possible to solve in any reasonable amount of time?

Thanks!

Answer 1

The problem you're describing ends up being NP-hard (via a reduction from the longest path problem), so unless P = NP there aren't going to be any algorithms that are correct on all inputs and efficient on all inputs. You'll either need to be willing to accept answers that aren't always correct (but might be approximately close) or will need to consider algorithms that are quick in some cases but quite slow in others.

There are some algorithms that work well for this problem as long as the paths aren't too long. The color-coding algorithm, for example, works well if the maximum path length isn't too long, but I'm concerned that length 500 is going to be way too large here. A quick Google search turned up this paper, which contains an algorithm for finding reasonably long paths in a graph and might be applicable here. But barring that, you may need to just do some random sampling and hope that everything works out.

If you know more about your graph - for example, if the edges obey the triangle inequality or if the edges all have values in some small finite range - you might be able to use other approaches. But barring that, I'm afraid you're not going to have many options open to you.

Sorry about that, but hope this helps!