Source: PARTITION
Target: SHORTEST WEIGHT-CONSTRAINED PATH
Motivation: Establishes NP-hardness of SHORTEST WEIGHT-CONSTRAINED PATH via polynomial-time reduction from PARTITION. The reduction encodes the subset-sum structure of PARTITION into a layered graph where choosing one of two parallel edges at each layer corresponds to including or excluding an element, with edge lengths and weights set so that a balanced partition exists if and only if the optimal constrained path achieves a specific length.
Reference: Garey & Johnson, Computers and Intractability, ND30, p.214

GJ Source Entry

[ND30] SHORTEST WEIGHT-CONSTRAINED PATH
INSTANCE: Graph G=(V,E), length l(e)∈Z^+, and weight w(e)∈Z^+ for each e∈E, specified vertices s,t∈V, positive integers K,W.
QUESTION: Is there a simple path in G from s to t with total weight W or less and total length K or less?
Reference: [Megiddo, 1979]. Transformation from PARTITION.
Comment: Also NP-complete for directed graphs. Both problems are solvable in polynomial time if all weights are equal or all lengths are equal.

Reduction Algorithm

Summary:
Given a PARTITION instance with multiset A = {a_1, a_2, ..., a_n} of positive integers with total sum S = sum(a_i), construct a SHORTEST WEIGHT-CONSTRAINED PATH instance as follows.

The target model is an optimization problem (minimize total path length subject to a weight budget), so the reduction produces an instance whose optimal length encodes whether a balanced partition exists.

Key idea (+1 offset): Since the target requires strictly positive edge lengths and weights (Z^+), we cannot use zero. Instead, every edge carries a "+1" offset: one edge has length a_i + 1 and weight 1, the other has length 1 and weight a_i + 1. This shifts all values away from zero. A path of n edges always accumulates exactly S + n total length-plus-weight. The weight bound absorbs exactly half of S plus the n offset units, so the optimal path length equals S/2 + n if and only if a balanced partition exists.

1. Graph construction: Create a chain of n + 1 vertices v_0, v_1, ..., v_n with s = v_0 and t = v_n. Between v_{i-1} and v_i, add two parallel edges:

   • "Include" edge: length = a_i + 1, weight = 1.
   • "Exclude" edge: length = 1, weight = a_i + 1.

2. Weight bound: Set W = floor(S / 2) + n (integer division).

3. Correctness (forward): If A can be partitioned into A_1, A_2 with sum(A_1) = sum(A_2) = S/2, then for each a_i in A_1 take the "include" edge (length a_i + 1, weight 1), and for each a_i in A_2 take the "exclude" edge (length 1, weight a_i + 1). Total length = sum(A_1) + n = S/2 + n. Total weight = sum(A_2) + n = S/2 + n = W. The weight constraint is satisfied with equality.

4. Correctness (reverse): Any s-t path selects exactly one edge per layer, so total_length + total_weight = S + 2n (every a_i + 1 appears exactly once in length, and 1 appears once in weight, or vice versa). To minimize length subject to weight <= W = floor(S/2) + n, we need weight <= floor(S/2) + n, hence length >= S + 2n - (floor(S/2) + n) = ceil(S/2) + n. Equality (length = ceil(S/2) + n) requires weight = floor(S/2) + n. When S is even, this gives length = S/2 + n, which requires the "include" set to sum to exactly S/2 — i.e., a balanced partition. When S is odd, floor(S/2) + n < S/2 + n, so weight = floor(S/2) + n is still achievable (take the larger half as "exclude"), and the optimal length is ceil(S/2) + n, but no balanced partition exists.

5. Detecting partition existence: The optimal path length is S/2 + n if and only if S is even and a balanced partition exists. Otherwise the optimal length is strictly greater than S/2 + n (or equals ceil(S/2) + n when S is odd). The caller can check optimal_length == S/2 + n with S even to determine feasibility.

Time complexity of reduction: O(n) to construct the graph.

Size Overhead

Symbols:

• n = num_elements (number of elements in the PARTITION instance)

The weight_bound is a computed field (floor(total_sum / 2) + n), not a size metric in the overhead table.

Validation Method

• Closed-loop test: reduce a PARTITION instance to ShortestWeightConstrainedPath, solve target with BruteForce, extract solution, verify on source.
• Test with known YES instance: A = {1, 2, 3, 4, 5, 5} with S = 20, n = 6. Weight bound = 10 + 6 = 16. Optimal length should be 10 + 6 = 16 (balanced partition exists).
• Test with known NO instance: A = {1, 2, 3, 7} with S = 13 (odd), n = 4. Weight bound = floor(13/2) + 4 = 10. Optimal length = ceil(13/2) + 4 = 11 > S/2 + n, confirming no balanced partition.
• All edge lengths and weights are >= 1, satisfying the Z^+ requirement.

Example

Source instance (PARTITION):
A = {2, 3, 4, 5, 6, 4} with S = 24, n = 6, S/2 = 12.
A valid partition: A_1 = {2, 4, 6} (sum = 12), A_2 = {3, 5, 4} (sum = 12).

Constructed target instance (ShortestWeightConstrainedPath):

• 7 vertices: v_0 = s, v_1, v_2, v_3, v_4, v_5, v_6 = t
• 12 edges (2 per layer), weight_bound W = 12 + 6 = 18:

Solution mapping:

• Partition A_1 = {2, 4, 6} (layers 1, 3, 5): use "include" edges
• Partition A_2 = {3, 5, 4} (layers 2, 4, 6): use "exclude" edges
• Total length: 3 + 1 + 5 + 1 + 7 + 1 = 18 = S/2 + n = 12 + 6
• Total weight: 1 + 4 + 1 + 6 + 1 + 5 = 18 = W
• Optimal length = 18 = S/2 + n, confirming balanced partition exists.

References

• [Megiddo, 1979]: Nimrod Megiddo (1979). "Combinatorial optimization with rational objective functions." Mathematics of Operations Research 4(4), pp. 414–424.