Structural Parameters of the Conflict Graph
Lax117284.Theorem4 · concepts/Lax117284/Theorem4.lean · lax-117284
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Theorem 4. The problem
- is NP-hard for a constant treewidth of the overall conflict graph,
- is fixed-parameter tractable with respect to ,
- and is fixed-parameter tractable with respect to the number of clients.
Hardness holds already under the bound , and therefore under every larger constant upper bound: it is obtained from Multicoloured Independent Set through the per-client problem, whose instances the construction produces with treewidth at most , and a reduction back to the uniform problem that raises the treewidth by at most . Tractability for is a dynamic program over a nice tree decomposition of the overall conflict graph, whose table holds, for every bag, the restrictions to that bag of the schedules of the subtree; a bag of clients admits of them. Tractability for is a formulation as an integer program whose number of variables depends on alone, which the source solves by Lenstra's algorithm; here it is solved by an algorithm for these particular integer programs.
The third bullet is stated in two halves: the problem parameterized by fpt-reduces to the feasibility of the integer programs of the reduction, parameterized by the number of variables (, proved: the integer program of the source, written by a word RAM program), and the feasibility of these integer programs is fixed-parameter tractable (, proved by enumerating parameter-bounded certificates and checking the reconstructed solutions for the matrices of the family, which are fixed by ; the source cites Lenstra's algorithm for it, which is not needed for this family). Fixed-parameter tractability in () is their combination.
Concept map
Evidence
In the paper
- page 3 of this submission's paper
Lean source view on GitHub
| 1 | import Lax117284.InstanceEncoding |
| 2 | import Lax117284.IlpClients |
| 3 | import Lax117284.ParameterizedComplexity |
| 4 | import Lax117284.Problems |
| 5 | |
| 6 | /-! |
| 7 | --- |
| 8 | title: Structural Parameters of the Conflict Graph |
| 9 | type: theorem |
| 10 | --- |
| 11 | **Theorem 4.** The problem |
| 12 | |
| 13 | * is NP-hard for a constant treewidth of the overall conflict graph, |
| 14 | * is fixed-parameter tractable with respect to , |
| 15 | * and is fixed-parameter tractable with respect to the number of clients. |
| 16 | |
| 17 | Hardness holds already under the bound , and therefore under every larger |
| 18 | constant upper bound: it is obtained from Multicoloured Independent Set through the per-client problem, |
| 19 | whose instances the construction produces with treewidth at most , and a reduction back |
| 20 | to the uniform problem that raises the treewidth by at most . Tractability for |
| 21 | is a dynamic program over a nice tree decomposition of the overall conflict |
| 22 | graph, whose table holds, for every bag, the restrictions to that bag of the schedules of |
| 23 | the subtree; a bag of clients admits of them. Tractability for |
| 24 | is a formulation as an integer program whose number of variables depends on alone, |
| 25 | which the source solves by Lenstra's algorithm; here it is solved by an algorithm for these |
| 26 | particular integer programs. |
| 27 | |
| 28 | The third bullet is stated in two halves: the problem parameterized by *fpt-reduces* to the |
| 29 | feasibility of the integer programs of the reduction, parameterized by the number of variables |
| 30 | (`byClients_fptReduces_ilp`, proved: the integer program of the source, written by a word RAM |
| 31 | program), and the feasibility of these integer programs is fixed-parameter tractable |
| 32 | (`IlpClients.ilpClients_fpt`, proved by enumerating parameter-bounded certificates and checking the reconstructed |
| 33 | solutions for the matrices of the family, which are fixed by ; the source cites Lenstra's algorithm for it, which is not |
| 34 | needed for this family). Fixed-parameter tractability in (`fpt_byClients`) is their |
| 35 | combination. |
| 36 | |
| 37 | # Formalization Notes |
| 38 | |
| 39 | The public decision and reduction statements use the archive's shared fixed-parameter |
| 40 | time definitions from `Lax496464`, including computable parameter bounds and binary |
| 41 | input size. The direct decision program enumerates schedules on short inputs; on the |
| 42 | remaining inputs it builds the integer program and runs the verified solver at a |
| 43 | sufficient word length. A proved bridge transfers these machine specifications to |
| 44 | the shared definitions. |
| 45 | |
| 46 | Hardness is stated at treewidth at most rather than for each separately. |
| 47 | The class of instances of treewidth at most is contained in that of treewidth at most |
| 48 | for every larger , so the statement at gives every other one; the source's |
| 49 | construction forcing the treewidth to be exactly serves the version of the claim in |
| 50 | which the parameter is pinned rather than bounded. |
| 51 | |
| 52 | The two tractability claims are claims about one program each, on the word encoding of an |
| 53 | instance, with the parameter a function of the word: the number of days plus the treewidth |
| 54 | of the overall conflict graph of the decoded instance, and the number of clients. The |
| 55 | number of days and the number of clients are entries of the word; the treewidth is a |
| 56 | structural property of what the word encodes, which is a function of the word because a word |
| 57 | encodes at most one instance. |
| 58 | |
| 59 | A word of the domain is an instance block followed by the single entry of the fairness |
| 60 | parameter, so the instance is decoded from the word without its last entry (`x.dropLast`); the |
| 61 | parameter itself is the last entry. Decoding the whole word would read no instance at all, since |
| 62 | the block has even length, and would make both problems trivial. |
| 63 | -/ |
| 64 | |
| 65 | namespace Lax117284.Theorem4 |
| 66 | |
| 67 | open Lax117284.Scheduling Lax117284.Problems Lax117284.InstanceEncoding |
| 68 | open Lax117284.ParameterizedComplexity |
| 69 | |
| 70 | /-- The problem parameterized by the number of days plus the treewidth of the overall |
| 71 | conflict graph. -/ |
| 72 | noncomputable def byDaysAndTreewidth : ParameterizedComplexity.Problem where |
| 73 | Domain := UniformInstances |
| 74 | Yes x := (decode x.dropLast).HasKFairSchedule (parameter x) |
| 75 | param x := (decode x.dropLast).days + ConflictGraph.treewidth (decode x.dropLast) |
| 76 | |
| 77 | /-- The problem parameterized by the number of clients. -/ |
| 78 | noncomputable def byClients : ParameterizedComplexity.Problem where |
| 79 | Domain := UniformInstances |
| 80 | Yes x := (decode x.dropLast).HasKFairSchedule (parameter x) |
| 81 | param x := (decode x.dropLast).clients |
| 82 | |
| 83 | /-- **Theorem 4, first bullet.** The problem is NP-hard on the instances whose overall |
| 84 | conflict graph has treewidth at most `6`, hence for a constant treewidth. -/ |
| 85 | axiom uniform_treewidth_npHard : |
| 86 | NPHard (Uniform fun I _ => ConflictGraph.treewidth I ≤ 6) |
| 87 | |
| 88 | /-- **Theorem 4, second bullet.** The problem is fixed-parameter tractable with respect to |
| 89 | the number of days plus the treewidth of the overall conflict graph. -/ |
| 90 | axiom fpt_byDaysAndTreewidth : FptDecision byDaysAndTreewidth |
| 91 | |
| 92 | /-- **Theorem 4, third bullet, the reduction.** The problem parameterized by the number of |
| 93 | clients fpt-reduces to the feasibility of the integer programs of the family `IlpClients.ilpClients`, |
| 94 | parameterized by the number of variables: the integer program of Theorem 21 of the source, with one |
| 95 | variable per type of day and set of clients and one slack per client, `2 ^ (n² + n) + n` variables in |
| 96 | all, computed by a word RAM program. -/ |
| 97 | axiom byClients_fptReduces_ilp : FptReduces byClients IlpClients.ilpClients |
| 98 | |
| 99 | /-- **Theorem 4, third bullet.** The problem is fixed-parameter tractable with respect to |
| 100 | the number of clients: by the reduction `byClients_fptReduces_ilp` and the algorithm for the |
| 101 | integer programs of the family, `IlpClients.ilpClients_fpt`. -/ |
| 102 | axiom fpt_byClients : FptDecision byClients |
| 103 | |
| 104 | end Lax117284.Theorem4 |
| 105 |
Formalization Notes
The public decision and reduction statements use the archive's shared fixed-parameter time definitions from , including computable parameter bounds and binary input size. The direct decision program enumerates schedules on short inputs; on the remaining inputs it builds the integer program and runs the verified solver at a sufficient word length. A proved bridge transfers these machine specifications to the shared definitions.
Hardness is stated at treewidth at most rather than for each separately. The class of instances of treewidth at most is contained in that of treewidth at most for every larger , so the statement at gives every other one; the source's construction forcing the treewidth to be exactly serves the version of the claim in which the parameter is pinned rather than bounded.
The two tractability claims are claims about one program each, on the word encoding of an instance, with the parameter a function of the word: the number of days plus the treewidth of the overall conflict graph of the decoded instance, and the number of clients. The number of days and the number of clients are entries of the word; the treewidth is a structural property of what the word encodes, which is a function of the word because a word encodes at most one instance.
A word of the domain is an instance block followed by the single entry of the fairness parameter, so the instance is decoded from the word without its last entry (); the parameter itself is the last entry. Decoding the whole word would read no instance at all, since the block has even length, and would make both problems trivial.
Builds on
Used by
none
From Mathlib
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments