Longest Path in Path of Exile

Question

Background: In the popular online video game Path of Exile, there is a skill tree that players can allocate points to as they gain levels. The skill tree is essentially a connected graph where a node is coloured "on" or "off" depending on whether a player has allocated that point or not. A player may begin at one of fifteen fixed locations in the graph, called starting nodes, by allocating it to be "on" and may only allocate a new node if it is connected to a node that is "on". The subgraph of "on" nodes are the allocated points. There are several special nodes scattered across the graph which are called jewel nodes.

Definitions: A path connecting nodes $a$ and $b$ is a connected subset of nodes containing $a$ and $b$. Given a path $P$ connecting nodes $a$ and $b$, the length of $P$ between $a$ and $b$ is the minimum number of edges in any subpath of $P$ connecting $a$ and $b$.

Question: What is the longest path from a starting node to a jewel node?

That is, what is the maximum length of a path that begins at one of the starting nodes and ends at a jewel node? I would like an algorithm for computing such a path, but I don't know if such an algorithm exists. The graph is sufficiently large and complicated that a naive brute force search is probably not feasible.

Inspiration: This question was inspired by this Reddit question. There is an item in the game which provides greater bonuses to the player for longer paths, so it is natural to want to maximise these bonuses.

Examples:

Here is a path of length 11.

Here is a path of length 17.

Answer 1

As you may already know, the longest-path problem on an arbitrary undirected graph is NP-hard. So a tractable solution here will need to exploit the specific structure of the Path of Exile passive "tree" (not actually a tree, since it contains cycles).

One idea is to divide and conquer. Let's say we partition the graph into $k$ subgraphs $G_1, \ldots, G_k$ so that for each $G_i$, the number of edges that connect a vertex of $G_i$ with a vertex not in $G_i$ is small. Let's call this set of edges $E_i$.

Let's assume WLOG that the longest path starts in $G_1$. This path can meander from subgraph to subgraph, crossing an edge in $E_1 \cap E_i$ into some other subgraph $G_i$, then leaving $G_i$ through some other edge in $E_i$, etc.

Let's look at one arbitrary subgraph $G_i$. Assuming that the path neither starts or ends in $G_i$ (if it does, that just adds some extra cases to consider), then we can describe all segments of the longest path inside $G_i$ by a set of pairs $P = \left\{(e_1, e_2), (e_3, e_4), \ldots \right\}$ of edges in $E_i$ where the segments enter and leave $G_i$. Note that $P$ is enough to completely determine the segments of the longest path inside $G_i$, using only local information in $G_i$, and no knowledge about any of the other subgraphs $G_j$.

So, for every possible $P$ (an upper bound on the number of sets of pairs is $|E_i|!$, hence why we want $E_i$ to contain few edges) we can precompute the segments with longest total length that connect those pairs of edges.

Once we've done this, we can "stitch together" the partial answers by searching via brute force over all paths on the multigraph formed by collapsing each $G_i$ into a single vertex.

Eyeballing the Path of Exile skill "tree" makes me somewhat optimistic that this partitioning can be made to work, since there are some obvious good cuts to choose to form the $G_i$: for instance you can cut six edges to excise the center portion of the "tree," eight edges to cut out the north outer region, etc.

Answer 2

Some approach which is too long for a comment.

Some remarks:

• We can reformulate the problem as: find the longest path $P$ connecting $a, b$ which has no proper subset which is also a path connecting $a, b$.
• We can always optimize the graph a little by throwing away all points not connected to $a, b$ and by removing “dangling points” i.e. points of degree 1 which are neither $a$ nor $b$.

Maybe one can start with $P$ being the whole graph and step-by-step removing vertices, making the path longer? Call a point $p \in P$ essential to $P$, if $P \setminus \{p\}$ is not a path from $a$ to $b$ anymore. Now I present a simple backtracking algorithm:

1. Start with $P$ being the whole set of vertices.

2. Find $Q \subseteq P$ a shortest path in $P$ which connects $a, b$.

3. Try to find a point $p \in Q$ which is not essential to $P$.

   • If such a point exists, set $P := P \setminus \{p\}$. Then go back to 2.
   • If no such point exists, we have found a candidate. Write $P$ down somewhere together with the length of $Q$. Now backtrack on the choices of $p$ and try to choose differently.

When backtracking, also write down each state of $P$ that was visited, so we don't visit a some set twice.

In the worst case, this algorithm will perform no better than brute-force. But in many cases it will be a bit quicker.