While this submission is a draft, it cannot be used by other submissions.

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.

Read the Lean proof on GitHub

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 HH that is the union of p+10Sp + 10 S 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.