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

FF(1,m)||ΣZj is strongly W[2]-hard for the number of machines

Lax434175.JitFlowShopW2 · concepts/Lax434175/JitFlowShopW2.lean · lax-434175

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

    Let GG be a graph on the vertices 0,…,n−10, \dots, n-1 and kk a number. Its closed-neighbourhood instance is the Hitting Set instance on the universe {0,…,n+1}\{0, \dots, n+1\} with the n+2n + 2 sets N[v]={v}∪N(v)N[v] = \{v\} \cup N(v) for v<nv < n, {n}\{n\} and {n+1}\{n+1\}, and the solution size k+2k + 2. A set of k+2k + 2 elements meets all of them exactly when it contains nn and n+1n + 1 and its other kk elements dominate GG. So for k≤nk \le n the graph has a dominating set of size kk exactly when the instance has a hitting set of size k+2k + 2, and the solution size is at least 22 and at most the universe, as the construction of lax-496464 needs.

    The word of (G,k)(G, k) in lax-496464 is the compressed sparse row form of GG followed by kk; it has n+1n + 1 offsets, so nn is less than its length. A word RAM program reads it and writes the numbers of the closed-neighbourhood instance (in the sense of JitFlowShopStandardJitFlowShopStandard): for every vertex vv it tests each u<nu < n for membership in N[v]N[v] by scanning the block of vv, so the members come out in increasing order and without repetitions. When k>nk > n, where there is no dominating set of size kk, it writes instead the numbers of the instance with one empty set and solution size 22, which has no hitting set. Then the word map of JitFlowShopStandardJitFlowShopStandard writes the standard word of the zoo instance of the construction. Its machine count is the solution size plus one, k+3k + 3 or 33.

    Theorem. pp-Dominating-Set fpt-reduces to FF(1,m)∣∣∑ZjFF(1,m) \mid\mid \sum Z_j parameterized by the number of machines mm, by a polynomial-time map with m≤k+3m \le k + 3 whose words have numbers at most 64(ℓ+1)464 (\ell + 1)^4 for ℓ\ell their length.

    Since pp-Dominating-Set is W[2]-complete (lax-496464), FF(1,m)∣∣∑ZjFF(1,m) \mid\mid \sum Z_j is W[2]-hard for mm, and strongly W[2]-hard: already on the words whose numbers are at most 64(ℓ+1)464 (\ell + 1)^4.

    The reduction starts from Dominating Set and not from Hitting Set because the binary word of a Hitting Set instance writes the universe size in binary, so the universe can be exponentially larger than the word, while the construction has more than nn jobs.

    Concept map
    76 concepts
    100%
    Compressed sparse row encoding of a graphA graph with a parameter appendedConjunctive normal formAssembling problems from fieldsOne family for serial and parallel batchingBatching problems in three-field notationBatch scheduling on a single machineCommunication delaysBounds on the number of machines and jobsDeadlinesForbidden times and input encodingsInterruption as a field of parallel-machineschedulingJust-in-time flow shops of lax-496464 as zooinstancesFF(1,m)||ΣZj is strongly NP-hard under thestandard readingFF(1,m)||ΣZj is strongly W[2]-hard for thenumber of machinesScheduling kernelsMaximizing the minimum machine loadMachine sets and multiprocessor tasksConstraint modules and objectivesNon-preemptive scheduling on parallelmachinesCompletion-time objectivesOnline scheduling as a gameScheduling with operationsOne family for parallel machines and shopsOne family for parallel machines with andwithout preemptionParallel machinesProblems on parallel machines in three-fieldnotationParameters along embeddingsPrecedence constraints and time lagsPreemptive scheduling on parallel machinesPreemptive shop problems in three-fieldnotationPreemptive shop schedulingOptimization problems and embeddingsSingle-machine scheduling with rejectionRelease datesPreemption with restarts on parallelmachinesParameters of the zoo's resultsThe kinds of results on scheduling problemsA single server with setup timesNo-idle shops and batch setup timesOne family for shops with and withoutpreemptionShop problems in three-field notationShop schedulingThe standard reading of scheduling instancesand schedulesThreshold reductions between objectivesTransportation delays and a transport robotScheduling problems as parameterizedproblems on wordsParameters of scheduling problemsThe Scheduling Zoo, shop problemsResults of The Scheduling Zoo, shopproblemsBinary encoding of an input and a certificateThe complexity class NPThe complexity class PBinary Encoding of an InstanceThe Construction of Section 8Just-in-Time Scheduling in a Two-StageFlexible Flow ShopHitting SetNP-Hardness, and Strong NP-Hardness, of aScheduling ProblemParameterized Problems andFPT-Reductions on a Word RAMTheorem 1Fixed-Parameter Time on the Word RAMFPT-Reductions, FPT, Hardness andCompletenessFinite Relational StructuresFirst-Order Formulas and the Classes Σ_tand Π_tModel Checking and Weighted FaginDefinabilityThe W-Hierarchy and the A-HierarchyClique, Independent Set and Dominating SetHitting SetDominating Set Is W[2]-CompleteNP-Hardness of a Problem on Words ofNumbersBinary encoding of finite wordsPolynomial-time computation by a wordRAMPolynomial-time computation by a TuringmachineThe word RAMComputing a function within a time boundParameterized Problems andFPT-Reductions on a Word RAM
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A
    Evidence

    Lean source view on GitHub

    1import Lax434175.JitFlowShopStandard
    2import Lax496464.WH_E3_DominatingSet
    3
    4/-!
    5---
    6title: FF(1,m)||ΣZj is strongly W[2]-hard for the number of machines
    7type: theorem
    8---
    9Let GG be a graph on the vertices 0,…,n−10, \dots, n-1 and kk a number. Its *closed-neighbourhood
    10instance* is the Hitting Set instance on the universe {0,…,n+1}\{0, \dots, n+1\} with the n+2n + 2 sets
    11N[v]={v}∪N(v)N[v] = \{v\} \cup N(v) for v<nv < n, {n}\{n\} and {n+1}\{n+1\}, and the solution size k+2k + 2.
    12A set of k+2k + 2 elements meets all of them exactly when it contains nn and n+1n + 1 and its
    13other kk elements dominate GG. So for k≤nk \le n the graph has a dominating set of size kk
    14exactly when the instance has a hitting set of size k+2k + 2, and the solution size is at least
    1522 and at most the universe, as the construction of lax-496464 needs.
    16
    17The word of (G,k)(G, k) in lax-496464 is the compressed sparse row form of GG followed by kk; it
    18has n+1n + 1 offsets, so nn is less than its length. A word RAM program reads it and writes the
    19numbers of the closed-neighbourhood instance (in the sense of `JitFlowShopStandard`): for every
    20vertex vv it tests each u<nu < n for membership in N[v]N[v] by scanning the block of vv, so the
    21members come out in increasing order and without repetitions. When k>nk > n, where there is no
    22dominating set of size kk, it writes instead the numbers of the instance with one empty set and
    23solution size 22, which has no hitting set. Then the word map of `JitFlowShopStandard` writes
    24the standard word of the zoo instance of the construction. Its machine count is the solution
    25size plus one, k+3k + 3 or 33.
    26
    27**Theorem.** pp-Dominating-Set fpt-reduces to FF(1,m)∣∣∑ZjFF(1,m) \mid\mid \sum Z_j parameterized by the
    28number of machines mm, by a polynomial-time map with m≤k+3m \le k + 3 whose words have numbers at
    29most 64(ℓ+1)464 (\ell + 1)^4 for ℓ\ell their length.
    30
    31Since pp-Dominating-Set is W[2]-complete (lax-496464), FF(1,m)∣∣∑ZjFF(1,m) \mid\mid \sum Z_j is W[2]-hard
    32for mm, and strongly W[2]-hard: already on the words whose numbers are at most
    3364(ℓ+1)464 (\ell + 1)^4.
    34
    35The reduction starts from Dominating Set and not from Hitting Set because the binary word of a
    36Hitting Set instance writes the universe size in binary, so the universe can be exponentially
    37larger than the word, while the construction has more than nn jobs.
    38-/
    39
    40namespace Lax434175.JitFlowShopW2
    41open Lax434175 Lax434175.Results Lax434175.ResultParameters
    42
    43/-- `FF(1,m)||ΣZj` is W[2]-hard in the number of machines on the standard reading. -/
    44-- zoo-result: {"problem": "FF(1,m)||\\sum Z_j", "param": "m", "claim": "is W[2]-hard", "note": "Dominating Set (W[2]-complete in lax-496464) fpt-reduces to it through the construction of lax-496464; the cited result says strongly W[2]-hard, which is proved as well (p315_r1_holds)."}
    45axiom wHard_m : WHard (StandardReading.ops.at ZooShops.p315) 2 (lift (Ops.m ZooShops.p315))
    46
    47/-- `FF(1,m)||ΣZj` is strongly W[2]-hard in the number of machines: the reduction writes
    48numbers at most a fixed power of the length of its output. -/
    49axiom p315_r1_holds : ZooShopsResults.p315_r1 StandardReading.ops
    50
    51end Lax434175.JitFlowShopW2
    52
    Show ProofShow Proof
    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.

    Loading discussion…