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.
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 instructions, where is the number of days plus the treewidth of the overall conflict graph, for a function of alone. The program is compiled from an IMP+ program whose correctness and cost are proved in ; the theorem of Bodlaender and Kloks that finds a nice tree decomposition of small width in time times a polynomial () is proved, in , from its proof in lax-689794.