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

Structural Parameters of the Conflict Graph

Lax117284.Theorem4 · concepts/Lax117284/Theorem4.lean · lax-117284

proven

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Natural Language Statement

    Theorem

    Theorem 4. The problem 1∣rep∣min⁡j∑iZi,j1 \mid \mathrm{rep} \mid \min_j \sum_i Z_{i,j}

    • is NP-hard for a constant treewidth τ\tau of the overall conflict graph,
    • is fixed-parameter tractable with respect to m+τm + \tau,
    • and is fixed-parameter tractable with respect to the number nn of clients.

    Hardness at constant treewidth holds already at τ=6\tau = 6, 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 44, and a reduction back to the uniform problem that raises the treewidth by at most 22. Tractability for m+τm + \tau 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 τ+1\tau + 1 clients admits 2O(τm)2^{O(\tau m)} of them. Tractability for nn is a formulation as an integer program whose number of variables depends on nn 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 nn fpt-reduces to the feasibility of the integer programs of the reduction, parameterized by the number of variables (byClientsfptReducesilpbyClients_fptReduces_ilp, proved: the integer program of the source, written by a word RAM program), and the feasibility of these integer programs is fixed-parameter tractable (IlpClients.ilpClientsfptIlpClients.ilpClients_fpt, proved by a guess-and-verify algorithm for the constraint matrices of the family, which are fixed by nn; the source cites Lenstra's algorithm for it, which is not needed for this family). Fixed-parameter tractability in nn (fptbyClientsfpt_byClients) is their combination.

    Concept map
    14 concepts
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A
    Evidence

    This concept declares 4 statements. Each proof establishes one of them relative to its assumptions.

    3 fpt_byDaysAndTreewidth proven

    In the paper

    • page 3 of this submission's paper

    Lean source view on GitHub

    1import Lax117284.InstanceEncoding
    2import Lax117284.IlpClients
    3import Lax117284.ParameterizedComplexity
    4import Lax117284.Problems
    5
    6/-!
    7---
    8title: Structural Parameters of the Conflict Graph
    9type: theorem
    10---
    11**Theorem 4.** The problem 1∣rep∣min⁡j∑iZi,j1 \mid \mathrm{rep} \mid \min_j \sum_i Z_{i,j}
    12
    13* is NP-hard for a constant treewidth τ\tau of the overall conflict graph,
    14* is fixed-parameter tractable with respect to m+τm + \tau,
    15* and is fixed-parameter tractable with respect to the number nn of clients.
    16
    17Hardness at constant treewidth holds already at τ=6\tau = 6, and therefore at every larger
    18constant: it is obtained from Multicoloured Independent Set through the per-client problem,
    19whose instances the construction produces with treewidth at most 44, and a reduction back
    20to the uniform problem that raises the treewidth by at most 22. Tractability for
    21m+τm + \tau is a dynamic program over a nice tree decomposition of the overall conflict
    22graph, whose table holds, for every bag, the restrictions to that bag of the schedules of
    23the subtree; a bag of τ+1\tau + 1 clients admits 2O(τm)2^{O(\tau m)} of them. Tractability for
    24nn is a formulation as an integer program whose number of variables depends on nn alone,
    25which the source solves by Lenstra's algorithm; here it is solved by an algorithm for these
    26particular integer programs.
    27
    28The third bullet is stated in two halves: the problem parameterized by nn *fpt-reduces* to the
    29feasibility 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
    31program), 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
    33of the family, which are fixed by nn; the source cites Lenstra's algorithm for it, which is not
    34needed for this family). Fixed-parameter tractability in nn (`fpt_byClients`) is their
    35combination.
    36
    37# Formalization Notes
    38
    39The combination of the two halves is not a general closure theorem. An fpt-reduction is only
    40required to run where its image fits in the word length, and the image here has a
    41parameter-sized table, so on a word much shorter than that table the decision program cannot run
    42the algorithm for the integer programs on the image; the proof of `fpt_byClients` handles those words, whose number
    43of schedules is bounded by a function of nn alone, by enumeration. On every other word it writes
    44the integer program and runs the algorithm for the integer programs on it at a word length chosen for that program.
    45
    46Hardness is stated at treewidth at most 66 rather than for each τ≥6\tau \ge 6 separately.
    47The class of instances of treewidth at most 66 is contained in that of treewidth at most
    48τ\tau for every larger τ\tau, so the statement at 66 gives every other one; the source's
    49construction forcing the treewidth to be exactly τ\tau serves the version of the claim in
    50which the parameter is pinned rather than bounded.
    51
    52The two tractability claims are claims about one program each, on the word encoding of an
    53instance, with the parameter a function of the word: the number of days plus the treewidth
    54of the overall conflict graph of the decoded instance, and the number of clients. The
    55number of days and the number of clients are entries of the word; the treewidth is a
    56structural property of what the word encodes, which is a function of the word because a word
    57encodes at most one instance.
    58
    59A word of the domain is an instance block followed by the single entry of the fairness
    60parameter, so the instance is decoded from the word without its last entry (`x.dropLast`); the
    61parameter itself is the last entry. Decoding the whole word would read no instance at all, since
    62the block has even length, and would make both problems trivial.
    63-/
    64
    65namespace Lax117284.Theorem4
    66
    67open Lax117284.Scheduling Lax117284.Problems Lax117284.InstanceEncoding
    68open Lax117284.ParameterizedComplexity
    69
    70/-- The problem parameterized by the number of days plus the treewidth of the overall
    71conflict graph. -/
    72noncomputable 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. -/
    78noncomputable 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
    84conflict graph has treewidth at most `6`, hence for a constant treewidth. -/
    85axiom 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
    89the number of days plus the treewidth of the overall conflict graph. -/
    90axiom fpt_byDaysAndTreewidth : FPT byDaysAndTreewidth
    91
    92/-- **Theorem 4, third bullet, the reduction.** The problem parameterized by the number of
    93clients fpt-reduces to the feasibility of the integer programs of the family `IlpClients.ilpClients`,
    94parameterized by the number of variables: the integer program of Theorem 21 of the source, with one
    95variable per type of day and set of clients and one slack per client, `2 ^ (n² + n) + n` variables in
    96all, computed by a word RAM program. -/
    97axiom byClients_fptReduces_ilp : byClients ≤fpt IlpClients.ilpClients
    98
    99/-- **Theorem 4, third bullet.** The problem is fixed-parameter tractable with respect to
    100the number of clients: by the reduction `byClients_fptReduces_ilp` and the algorithm for the
    101integer programs of the family, `IlpClients.ilpClients_fpt`. -/
    102axiom fpt_byClients : FPT byClients
    103
    104end Lax117284.Theorem4
    105
    Show ProofShow ProofShow ProofShow Proof
    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 fptbyClientsfpt_byClients handles those words, whose number of schedules is bounded by a function of nn 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 66 rather than for each τ≥6\tau \ge 6 separately. The class of instances of treewidth at most 66 is contained in that of treewidth at most τ\tau for every larger τ\tau, so the statement at 66 gives every other one; the source's construction forcing the treewidth to be exactly τ\tau 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 (x.dropLastx.dropLast); 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.

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…