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 at constant treewidth holds already at , and therefore at every larger constant: 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 a guess-and-verify algorithm for the constraint 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 at constant treewidth holds already at , and therefore at every larger |
| 18 | constant: 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 a guess-and-verify algorithm for the constraint matrices |
| 33 | 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 combination of the two halves is not a general closure theorem. An fpt-reduction is only |
| 40 | required to run where its image fits in the word length, and the image here has a |
| 41 | parameter-sized table, so on a word much shorter than that table the decision program cannot run |
| 42 | the algorithm for the integer programs on the image; the proof of `fpt_byClients` handles those words, whose number |
| 43 | of schedules is bounded by a function of alone, by enumeration. On every other word it writes |
| 44 | the integer program and runs the algorithm for the integer programs on it at a word length chosen for that program. |
| 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 : FPT 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 : byClients ≤fpt 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 : FPT byClients |
| 103 | |
| 104 | end Lax117284.Theorem4 |
| 105 |
Formalization Notes
The combination of the two halves is not a general closure theorem. An fpt-reduction is only required to run where its image fits in the word length, and the image here has a parameter-sized table, so on a word much shorter than that table the decision program cannot run the algorithm for the integer programs on the image; the proof of handles those words, whose number of schedules is bounded by a function of alone, by enumeration. On every other word it writes the integer program and runs the algorithm for the integer programs on it at a word length chosen for that program.
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