Proof of `The reduction can be computed in polynomial time`
groundedproofs/Lax762056Proofs/ReductionTime.lean · lax-762056
What this proof establishes
no assumptions
Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.
Description
Enumerate the retained vertices and their adjacency matrix, then add the offset to the threshold. The enumeration and adjacency tests take polynomial time.