Algorithm design: find any path in an undirected acyclic graph which has a total sum of the nodes as a specific value

Question

The question was asked in an interview, and I'm not sure if this is the most optimized answer, but here goes-

You have an undirected acyclic graph, where each node has a non-negative value x and the edges have 0 value. You need to find a path with any number of nodes on it such that the total sum of all node values is exactly k. There are N nodes in the graph. You can start at any node.

I gave the brute-force solution for this problem, which is basically do a dfs on each node until you find a valid "root" node, such that it has a path to one of the other nodes, with a total sum being k. The time complexity of this solution would be n^2, since we are doing DFS on each node.

The question was posed as a delivery problem, where you have N connected houses, each having a package of weight within the range 1 to k, and the truck can start at any house and should follow a path, and has to pick the package from every house that is on that path. The weights should sum exactly to k.

Answer 1

There's a solution in pseudo-polynimial $O(nk)$. First, you can safely delete every node of the graph with weight bigger than $k$. For each node $v$ keep an array $A[v]$ of size $k$, where $A[v][i]$ says how many children $u$ of $v$ have paths that start in $u$ (a node $u$ is the start of a path $u_1, \ldots, u_m$ if $u = u_1$ and $u_{i+1}$ is a child of $u_i$ for all $i$) and whose weight is exactly $i$. Also, let $w$ be the function that maps nodes to their weights.

Your graph is a bunch of trees, and you can process each of them individually. For a given tree, choose an arbitrary node as the root, and do dynamic programming in the following way to fill up $A$. For any node $v$ we have that

$$ A[v][i] = \sum_{u \text { is a child of } v} \big[ A[u][i - w(u)] \geq 0\big] $$

If for some $v$ it holds that $A[v][k-w(v)] \geq 1$ we are done. This corresponds to the case where there is a path that starts in $v$ and has weight $k$. It could be however, that the path of weight $k$ we are looking for does not start in $v$, but it rather has $v$ as its closest node to the root. In order to detect this, we can process the tree from bottom to top. We denote the parent of a node $u$ as $p(u)$. For each node $u$, if there is some $j$ such that $1 \leq j \leq w(u)$ and $A[u][j-w(u)]$, then we know there is a path of weight $j$ that starts in $u$. We call this path $\pi_1$. So we only need to check whether there is a path $\pi_2 \neq \pi_1$ of weight $k-j-w(p(u))$ that starts from a child of $p(u)$. This corresponds to check the value of $A[p(u)][k-j-w(p(u))]$. Note that it could happen that $w(\pi_1) = w(\pi_2)$, in which case we would need to check whether $A[p(u)][k-j-w(p(u))] \geq 2$.

Thanks to @j_random_hacker for the suggestions on how to improve the algorithm.

Answer 2

I'm going to assume the graph is of bounded degree, specifically $d = 3$ (i.e. a binary tree). It could be any bounded degree, but it's easier to visualize with a binary tree. If the degree is unbounded, then this becomes slower.

---

Algorithm

First thing is to root the tree, preferably with a node that splits the tree evenly among its subtrees. That is, its subtrees have the same size. Though this is not required as we can still do an average case analysis.

Next, compute partial sums for each node except the root node (let it be 0). Specifically, the partial sum of each node is the value of the node plus the partial sum of its parent. For a node $v$ this is represented by $p(v)$:

$$p(v) = \text{val}(v) + p(\text{parent}(v))$$

This can be done with a DFS. Let's call the list of partial sums in the left subtree $L$ and the list of partial sums in the right subtree $R$. Choose whichever list is smaller, let's say that is $L$.

Now, sort $L$ and sort $R$. Then using the two pointer method (see method 4 here), we walk from smallest to largest in $L$ and largest to smallest in $R$ looking for the value $k - \text{val}(u)$. Where $u$ is the root node (since it was not included in the partial sums, we must add it back in, or rather subtract it out).

If we find this value, return the two nodes $L$ and $R$ where it was found. The path between these two nodes, through $u$, are a path of value $k$.

If we do not find this value, we know the path of value $k$ does not contain our root node $u$. Thus, we recurse on both (or all) subtrees.

With a binary tree, on average the recurrence would be:

$$\begin{align} T(n) = 2T(n/2) + n\log n\\ \end{align}$$

Which comes out to $T(n) = O(n (\log n)^2)$.

If the degree is not bounded then instead of just scanning $L$ and searching in $R$ we'd have to do this for all pairs of subtrees. Thus, on average we have:

$$T(n) = kT(n/k) + k^2 n \log n$$

Where $k$ is the branching factor.

You could possibly get better bounds by realizing that the average size of $L$ and $R$ for all pairs of subtrees would be $n/k$ thus bringing us to:

$$T(n) = kT(n/k) + k n \log n$$

---

Example 1

Let's say we have the following graph and $k = 74$

First, root the tree

Second, compute partial sums

Now we have:

$L = [2, 7, 9, 28, 32, 69]$

$R = [3, 14, 16, 20, 45, 51, 86, 88]$

Third, scan through $L$ and $R$ searching for $74 - 1 = 73$

1. 2 + 88 = 90 > 73, decrement $r$
2. 2 + 86 = 88 > 73, decrement $r$
3. 2 + 51 = 53 < 73, increment $l$
4. 7 + 51 = 58 < 73, increment $l$
5. 9 + 51 = 60 < 73, increment $l$
6. 28 + 51 = 79 > 73, decrement $r$
7. 28 + 45 = 73!

We've found 73, so we know a path of value 74 starts where $p(s) = 28$ and ends where $p(t) = 45$. This path is: $[19, 7, 2, 1, 3, 13, 29]$.

---

Example 2

Let's say in the prior example, $k = 113$. In the third step, we would not find the correct value, so we'd recurse on:

And:

We wouldn't find a solution in the left subgraph since the sum of all values is less than $k$. We can root the right subtree as:

We wouldn't find it crossing 13, so we'd recurse again on:

And:

The left subtree can be thrown out for the same reason we did earlier. Then we would immediately find it in the right subtree as $[41, 29, 43]$ for a path of value 113.

---

Optimizations

Miscellaneous optimizations are shown here.

Delete large nodes

You can also do what Bernardo suggested by deleting all nodes with value larger than $k$ then call this algorithm on each remaining tree in the forest.

Delete small trees

You can also ignore an entire tree (or subtree) if the sum of all nodes in that subtree is less than $k$.

Root all trees as binary trees

When computing partial sums, since we are not including the root node, we can use this step and convert it into a binary tree (at least from the root's perspective) by adding at most a linear number of nodes.

If the root has $d$ children, then we create a balanced binary tree with $d$ leaves where the leaf nodes are those $d$ children and all other nodes are value 0. We compute the partial sums and follow that formula above to determine if it crosses the root node of this new tree.

For example:

Would convert to:

Then the algorithm would tell you if the path spans the root node (in read) which really means "does this path go from the children [1, 2, 3, 4] to the children [5, 6, 7, 8]?". Then if the answer is no, you recurse on the following:

And:

With this optimization we can bring the recurrence (even without bounded degree) back to:

$$T(n) = 2T(\lceil n/2 \rceil) + n \log n$$

Which again results in $T(n) = O( n (\log n)^2)$.

Sort while computing $p(v)$

You can sort implicitly by running Dijkstra's algorithm instead of just doing a dfs. This won't asymptotically be an improvement however since it will still take $O(V \log V) = O(n \log n)$ to run Dijkstra's.