2
$\begingroup$

This problem comes up in the context of game skilltrees, for example in Path of Exile. In this case, one wants to have a subgraph of the entire graph that connects all desired nodes to the origin, but contains as few nodes as possible. Is there an efficient algorithm for this, or a good heuristic? Or is it, as I suspect, NP-hard?

Simply using Dijkstra to determine the distances and then Kruskal to find a minimum spanning tree does not work. This is because the cost of connecting a subsequent node can depend on what nodes are already connected (and by which paths).

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
1
$\begingroup$

You are talking about the Steiner tree problem. The decision problem is as follows:

Given a graph $G = (V, E)$ and a set of terminal vertices $T \subseteq V$ and a integer $k$, does there exist a set of at most $k$ edges $F \subseteq E$ such that $G' = (T, F)$ is connected.

The problem is indeed NP-complete, but on the positive side, it is solvable in fixed parameter tractable time $O(3^k (n+m))$.

There is an approximation algorithm too.

Improve this answer
$\endgroup$
0
$\begingroup$

As already said, that is the (NP-hard) Steiner tree problem in graphs. If you just care about the number of included vertices, you can simply set all edge weights to 1. Please note that NP-hard does not mean at all that it is not efficiently solvable in practice. Under "External links" on https://en.wikipedia.org/wiki/Steiner_tree_problem you find some efficient exact solvers for this problem, which provide optimal solutions to Steiner tree problems with tens of thousands of edges within seconds.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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