Star Sum Problem

computation graph-theory

Definition

Star Sum Problem

Let be a graph consisting of a set of vertex-disjoint stars and let be a target integer. The star sum problem is a decision problem asking whether there exists a subset of stars in such that the total number of vertices in is precisely .

Example Instance: Below is a graph made of 4 disjoint stars ( to ) and a target integer . A valid solution subset would be since , or since .

Relation to Subset Sum

The star sum problem is essentially a graph-theoretic formulation of the subset sum problem. Because the stars are strictly vertex-disjoint, the structural properties of the stars (such as their edges) are irrelevant; each star in can be abstracted as merely its vertex count .

Consider a concrete instance where we want to find a subset summing to . By choosing the integer and from the set, we conceptually pick the stars and which precisely combine to vertices total.

Equivalence to Subset Sum Problem

The star sum problem is equivalent (w.r.t. polynomial time reduction) to the subset sum problem. Therefore, it is also NP-complete.

Let an instance of the subset sum problem be given by a multiset of positive integers and a target sum .

In polynomial time, we construct a graph as follows: for each integer , create a star graph component with exactly vertices (which corresponds to the complete bipartite graph , or if ). All constructed stars are strictly vertex-disjoint. We keep the same target integer .

Correctness: Picking a subset of stars in whose vertices sum to exactly directly corresponds to picking a subset of integers in that sum to exactly .

Let an instance of the star sum problem be given by a graph consisting of vertex-disjoint stars and a target .

In polynomial time, count the number of vertices for each star in . We construct a subset sum instance with the multiset and the same target sum .

Correctness: Picking a subset of integers from summing to exactly identically mirrors selecting the corresponding stars in to obtain exactly vertices.

Approaches

Since the problem is a direct mapping to the subset sum problem, the exact same algorithmic approaches apply:

Brute-force

A brute-force approach evaluates all possible subsets of the stars to check if their vertices sum to exactly .

Time complexity:

Dynamic Programming

The problem can be solved in pseudo-polynomial time using dynamic programming.

Algorithm:
Given a collection of disjoint stars, we can evaluate all achievable vertex sums incrementally:

1. Initialisation: Start by marking all stars as “unprocessed” and construct an empty list (or set) of integers.
   Intuition: We will process the stars one by one and keep track of all possible numbers we could get by choosing any subset of them. Observe that while the number of possible choices of can be , the number of possible numbers we can get is bounded.
2. Iteration: Repeatedly process unprocessed stars (in an arbitrary order) as follows:
   • Choose an unprocessed star and read the number of its vertices (say it is ).
   • Construct by having it contain the increment of by .
   • Update by setting .
3. Termination: After all stars are processed, output YES if and only if contains .

Visual Step-by-Step Example:
Consider stars with vertex counts and target .

Time complexity: . The size of is bounded by the total sum of all vertices. Assuming each of the stars has at most vertices, is at most . We update it times, yielding an runtime.

Why is this Dynamic Programming?

While it may look like we are simply building a set, this procedure is fundamentally a dynamic programming approach. It incrementally constructs a table of boolean values where the state is “can we reach sum using a subset of the first stars?“.

Specifically, keeping track of the achievable sums in the set after processing stars is mathematically identical to storing a boolean array DP[i][j] (which is True if sum is achievable using the first stars). The transition directly corresponds to the DP recurrence DP[i][j] = DP[i-1][j] OR DP[i-1][j-c]. By only keeping track of the “True” values in a set (which bounds our runtime), we optimize the sparse DP table.

Constructing the Solution (Witness):

Once we know that the target sum is achievable (i.e., we get a YES answer), we typically want to reconstruct the actual subset that yields this sum. There are two general approaches that apply to almost all dynamic programming algorithms:

1. Backtracking: Once we find at the very end, we backtrack through the computation steps to see which elements allowed us to obtain . If we are at sum after processing a star of size , the sum could either come from (meaning we included this star) or it was already in before processing (meaning we skipped it).

2. Explicit Storage: Alternatively, for each intermediate sum in , we can simply store one subset which sums up to . Whenever we construct by adding (from star ) to a previous sum , we also record .

This approach makes returning the final solution completely trivial (just look up the set for key ), at the cost of significantly higher memory consumption.