A Fast and Correct Gather Algorithm

2026-03-14 Updated 2026-03-20 #Botting #Math #polygen

This document formally describes an optimal algorithm to solve the Maximum Weight Bounded-Size Subtree problem. By leveraging the properties of the Depth-First Search (DFS) sequence (preorder traversal), the algorithm flattens the tree into a 1D array. This transformation reduces the traditional complex tree-based backpack merging process into a standard sequence Dynamic Programming (DP) algorithm, achieving a deterministic $𝑂 (| 𝑉 | \cdot 𝑁)$ time complexity.

Definition 1 (Maximum Weight Bounded-Size Subtree)

Let $𝑇 = (𝑉, 𝐸)$ be a rooted tree with a designated root node $𝑟 \in 𝑉$ . Each node $𝑣 \in 𝑉$ is assigned a real-valued weight $𝑤 (𝑣) \in ℝ$ . Given a capacity integer $𝑁$ ( $1 \leq 𝑁 \leq | 𝑉 |$ ), the objective is to find a subset of vertices $𝑆 \subseteq 𝑉$ such that:

$𝑟 \in 𝑆$ .
The subgraph induced by $𝑆$ is connected in $𝑇$ .
$| 𝑆 | \leq 𝑁$ .

The goal is to maximize the total weight of the selected subset:

𝑊 (𝑆) = \sum_{𝑣 \in 𝑆} 𝑤 (𝑣) .

Note that the connectivity constraint, combined with the requirement that $𝑟 \in 𝑆$ , implies a strict topological dependency: for any node $𝑣 \in 𝑆 ∖ {𝑟}$ , its parent $𝑝 (𝑣)$ must also be in $𝑆$ .

The algorithm transforms the tree structure into a one-dimensional array using a Preorder Traversal (DFS sequence). Let $| 𝑉 | = 𝑀$ .

Let $𝑣_{1}, 𝑣_{2}, \dots, 𝑣_{𝑀}$ be the sequence of vertices in the order they are visited during a DFS preorder traversal, where $𝑣_{1} = 𝑟$ . Let $sz (𝑣)$ denote the total number of nodes in the subtree rooted at $𝑣$ .

We define a 2D dynamic programming table $𝐷$ . Let $𝐷_{𝑖, 𝑗}$ be the maximum weight obtained by selecting exactly $𝑗$ nodes from the suffix of the DFS sequence $𝑣_{𝑖}, 𝑣_{𝑖 + 1}, \dots, 𝑣_{𝑀}$ , assuming that the dependency path from the root down to the parent of $𝑣_{𝑖}$ has already been selected.

For a given index $𝑖 \in [2, 𝑀]$ and size $𝑗 \in [1, 𝑁]$ , we have two choices regarding the current node $𝑢 = 𝑣_{𝑖}$ :

Include $𝑢$ : We gain its weight $𝑤 (𝑢)$ , consume 1 unit of capacity, and proceed to evaluate the very next node in the DFS sequence $𝑣_{𝑖 + 1}$ . Thus, the maximal weight is $𝐷_{𝑖 + 1, 𝑗 - 1} + 𝑤 (𝑢)$ .
Exclude $𝑢$ : If we do not select $𝑢$ , the connectivity dependency dictates that we cannot select any node in the subtree of $𝑢$ . Since the subtree of $𝑢$ occupies exactly the contiguous block from index $𝑖$ to $𝑖 + sz (𝑢) - 1$ in the preorder sequence, we must skip this entire block. The next available valid node is precisely at index $𝑖 + sz (𝑢)$ . Thus, the maximal weight is $𝐷_{𝑖 + sz (𝑢), 𝑗}$ .

Combining these, the optimal sub-structure is given by the Bellman equation:

𝐷_{𝑖, 𝑗} = max {𝐷_{𝑖 + 1, 𝑗 - 1} + 𝑤 (𝑣_{𝑖}), 𝐷_{𝑖 + sz (𝑣_{𝑖}), 𝑗}}

By definition, the root $𝑟 = 𝑣_{1}$ must be included. Therefore, we do not have the option to exclude it:

𝐷_{1, 𝑗} = 𝐷_{2, 𝑗 - 1} + 𝑤 (𝑣_{1}) for 1 \leq 𝑗 \leq 𝑁

For any index $𝑖 \in [1, 𝑀 + 1]$ , choosing $𝑗 = 0$ nodes yields a weight of $0$ : $𝐷_{𝑖, 0} = 0$ . For any conceptually invalid state, the table is initialized to $- \infty$ .

Theorem 2 (Correctness)

The D tables correctly compute the maximum weight subtree satisfying the connectivity and capacity constraints.

Proof. By the properties of DFS preorder traversal, a parent node $𝑢$ always appears before any of its descendants. Furthermore, the descendants of $𝑢$ form a contiguous subarray $[𝑖, 𝑖 + sz (𝑢) - 1]$ in the sequence.

The connectivity constraint dictates that if a node $𝑢$ is not selected, no node in its subtree can be selected. The transition explicitly models this: exclusion of node $𝑣_{𝑖}$ forces the state transition to $𝑖 + sz (𝑣_{𝑖})$ , completely bypassing all descendants of $𝑣_{𝑖}$ . Inclusion of $𝑣_{𝑖}$ evaluates the contiguous node $𝑖 + 1$ (allowing the selection of its children). Since the root $𝑣_{1}$ is forcibly included, the subgraph generated by this sequence of decisions is guaranteed to form a single connected component containing the root. By Bellman’s Principle of Optimality, evaluating both choices ensures global topological optimization.⁠ $□$

Theorem 3 (Complexity)

The proposed algorithm has a time complexity of

𝑂 (| 𝑉 | \cdot 𝑁)

and a space complexity of

𝑂 (| 𝑉 | \cdot 𝑁)

Proof. The DFS traversal to generate arrays $𝑣_{𝑖}$ and $sz$ takes $𝑂 (| 𝑉 |)$ time. The DP table has $(| 𝑉 | + 2)$ rows and $(𝑁 + 1)$ columns. Each cell $𝐷_{𝑖, 𝑗}$ is computed in $𝑂 (1)$ time by comparing at most two previously computed values. Therefore, filling the table takes $𝑂 (| 𝑉 | \cdot 𝑁)$ operations. Finding the maximum value among $𝐷_{1, 𝑗}$ ( $1 \leq 𝑗 \leq 𝑁$ ) takes $𝑂 (𝑁)$ . Overall time complexity is $𝑂 (| 𝑉 | \cdot 𝑁)$ .

The algorithm strictly maintains an array $𝐷$ of size $(| 𝑉 | + 2) \times (𝑁 + 1)$ and auxiliary arrays of size $𝑂 (| 𝑉 |)$ . Thus, the memory footprint is bounded by $𝑂 (| 𝑉 | \cdot 𝑁)$ .⁠ $□$