Proof of `Multicoloured Independent Set`
groundedproofs/Lax117284Proofs/McisHard/Final.lean · lax-117284
What this proof establishes
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
Multicoloured Independent Set on the instances in normal form is NP-hard, by a many-one reduction from [2,3]-bounded 3-satisfiability: a formula is sent to the graph that is the union of copies of the port graph of the formula's occurrences (every position with five gadget ports, a matched pair of ports joining two gadgets and making two positions adjacent), which is regular, has an independent transversal exactly when the formula is satisfiable, and is written bit by bit by a word RAM program.