Proof of `Nice Tree Decompositions of Small Width Are Found in Fixed-Parameter Time`

groundedproofs/Lax117284Proofs/BodlaenderProved.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

Bodlaender's theorem with Kloks' niceness for the overall conflict graph of an instance, on a word RAM: the case of Lax689794.Bodlaender.niceDecompositioncomputableLax689794.Bodlaender.niceDecomposition_computable of lax-689794, which runs the exact Bodlaender–Kloks algorithm on a verified virtual machine, for the graph overallGraphIoverallGraph I on the I.clientsI.clients vertices.