Minimum Weighted Subgraph With the Required Paths II - Solution & Explanation

Problem Overview: You are given a weighted structure where certain paths must exist between specific nodes. The task is to select a subgraph with the minimum total weight that still preserves all required paths. Because the structure forms a tree and the number of required path constraints is small, the problem becomes a state-compression dynamic programming problem over the tree.

Approach 1: Brute Force Subgraph Enumeration (Exponential Time, Exponential Space)

The naive idea is to enumerate every possible subset of edges and check whether the resulting subgraph still satisfies all required paths. For each subset, run connectivity checks using DFS to verify that every required pair of nodes remains connected. Track the total edge weight and keep the minimum valid configuration. This approach requires checking up to 2^E edge subsets, and each validation costs O(n) using DFS, resulting in roughly O(2^E * n) time and O(n) auxiliary space. It quickly becomes infeasible even for moderate tree sizes but helps clarify the constraint that the chosen subgraph must preserve multiple connectivity requirements.

Approach 2: Tree Dynamic Programming with Bitmask States (O(n · 2^k) Time, O(n · 2^k) Space)

The optimized solution leverages the fact that the graph is a tree and the number of required paths k is small. Assign each required path an index and represent satisfied requirements using a k-bit mask. Perform a Depth-First Search from an arbitrary root. For every node, maintain a DP table where dp[node][mask] represents the minimum cost of the subtree that satisfies the set of path constraints encoded in mask.

During DFS, process children one by one and merge their DP states with the current node using bitmask transitions. When combining two states, compute the union of their masks with a bitwise OR operation and add the edge weight if the edge must be included to maintain connectivity. This is a classic state-compression technique using Bit Manipulation combined with subtree aggregation on a Tree. Because each node processes up to 2^k masks and merges with children states, the total complexity becomes O(n · 2^k) time with O(n · 2^k) memory.

Recommended for interviews: Interviewers expect the tree DP with bitmask compression. Starting with brute force demonstrates understanding of the constraint space, but the optimal solution shows you recognize two key signals: the structure is a tree and the number of required conditions is small enough for state compression. Combining DFS traversal with bitmask DP is the standard pattern for these problems.