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 holds already under the bound τ≤6\tau \le 6, 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 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 enumerating parameter-bounded certificates and checking the reconstructed solutions for the 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
    19 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.

    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 holds already under the bound τ≤6\tau \le 6, and therefore under every larger
    18constant upper bound: 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 enumerating parameter-bounded certificates and checking the reconstructed
    33solutions for the matrices of 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 public decision and reduction statements use the archive's shared fixed-parameter
    40time definitions from `Lax496464`, including computable parameter bounds and binary
    41input size. The direct decision program enumerates schedules on short inputs; on the
    42remaining inputs it builds the integer program and runs the verified solver at a
    43sufficient word length. A proved bridge transfers these machine specifications to
    44the shared definitions.
    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 : FptDecision 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 : FptReduces byClients 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 : FptDecision byClients
    103
    104end Lax117284.Theorem4
    105
    Show ProofShow ProofShow ProofShow Proof
    Formalization Notes

    The public decision and reduction statements use the archive's shared fixed-parameter time definitions from Lax496464Lax496464, 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 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…