The tempting inference is simple: Subset Sum is weakly NP-hard, and Subset Sum reduces to ILP, so perhaps ILP must also be weakly NP-hard. The first two facts are correct. The conclusion is not.
The arrow gives a lower bound
says that an algorithm for can solve after translating the input. Therefore,
The conclusion is at least NP-hard. The reduction supplies no upper bound on . In particular, the adjective weak does not travel along the arrow.
The target has more room
The reduction maps source instances into only part of the target’s instance space:
Those translated instances may capture hardness caused by large binary numbers. The target may also contain other instances whose hardness survives even when every number is small. A reduction from a weakly NP-hard problem does not inspect or rule out this additional structure.
To classify as weakly NP-hard, one needs more than an NP-hardness reduction. One must also show the tractable side of the claim, typically a pseudo-polynomial algorithm or polynomial-time solvability under unary encoding.
ILP needs the second reduction
The Subset Sum reduction to ILP uses coefficients . Their binary magnitude carries the source problem’s weak hardness. This proves ordinary NP-hardness, but says nothing against stronger hardness.
The Vertex Cover reduction to ILP uses only binary variables, coefficients from , and a bound . The numbers remain small, yet the reduction is still NP-hard. This establishes strong NP-hardness.
The corrected mental model is directional: a reduction tells us how low the target cannot fall. It does not tell us how much higher the target’s hardness may rise.