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

Proof of `Structural Parameters of the Conflict Graph` (3rd statement)

groundedproofs/Lax117284Proofs/Theorem4_Treewidth.lean · lax-117284

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.

Read the Lean proof on GitHub

In the paper

  • page 5 of this submission's paper

Description

The problem of the number of days plus the treewidth is fixed-parameter tractable. A word RAM program computes the answer within c∗gk∗(∣x∣+1)cc * g k * (|x| + 1) ^ c instructions, where kk is the number of days plus the treewidth of the overall conflict graph, for a function gg of kk alone. The program is compiled from an IMP+ program whose correctness and cost are proved in Machine/Tw∗.leanMachine/Tw*.lean; the theorem of Bodlaender and Kloks that finds a nice tree decomposition of small width in time 2O(w3)2^{O(w^3)} times a polynomial (Lax117284.Bodlaender.niceDecompositioncomputableLax117284.Bodlaender.niceDecomposition_computable) is proved, in BodlaenderProved.leanBodlaenderProved.lean, from its proof in lax-689794.