FF(1,m)||ΣZj is strongly W[2]-hard for the number of machines
Lax434175.JitFlowShopW2 · concepts/Lax434175/JitFlowShopW2.lean · lax-434175
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Let be a graph on the vertices and a number. Its closed-neighbourhood instance is the Hitting Set instance on the universe with the sets for , and , and the solution size . A set of elements meets all of them exactly when it contains and and its other elements dominate . So for the graph has a dominating set of size exactly when the instance has a hitting set of size , and the solution size is at least and at most the universe, as the construction of lax-496464 needs.
The word of in lax-496464 is the compressed sparse row form of followed by ; it has offsets, so is less than its length. A word RAM program reads it and writes the numbers of the closed-neighbourhood instance (in the sense of ): for every vertex it tests each for membership in by scanning the block of , so the members come out in increasing order and without repetitions. When , where there is no dominating set of size , it writes instead the numbers of the instance with one empty set and solution size , which has no hitting set. Then the word map of writes the standard word of the zoo instance of the construction. Its machine count is the solution size plus one, or .
Theorem. -Dominating-Set fpt-reduces to parameterized by the number of machines , by a polynomial-time map with whose words have numbers at most for their length.
Since -Dominating-Set is W[2]-complete (lax-496464), is W[2]-hard for , and strongly W[2]-hard: already on the words whose numbers are at most .
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 jobs.
Concept map
Evidence
Lean source view on GitHub
| 1 | import Lax434175.JitFlowShopStandard |
| 2 | import Lax496464.WH_E3_DominatingSet |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: FF(1,m)||ΣZj is strongly W[2]-hard for the number of machines |
| 7 | type: theorem |
| 8 | --- |
| 9 | Let be a graph on the vertices and a number. Its *closed-neighbourhood |
| 10 | instance* is the Hitting Set instance on the universe with the sets |
| 11 | for , and , and the solution size . |
| 12 | A set of elements meets all of them exactly when it contains and and its |
| 13 | other elements dominate . So for the graph has a dominating set of size |
| 14 | exactly when the instance has a hitting set of size , and the solution size is at least |
| 15 | and at most the universe, as the construction of lax-496464 needs. |
| 16 | |
| 17 | The word of in lax-496464 is the compressed sparse row form of followed by ; it |
| 18 | has offsets, so is less than its length. A word RAM program reads it and writes the |
| 19 | numbers of the closed-neighbourhood instance (in the sense of `JitFlowShopStandard`): for every |
| 20 | vertex it tests each for membership in by scanning the block of , so the |
| 21 | members come out in increasing order and without repetitions. When , where there is no |
| 22 | dominating set of size , it writes instead the numbers of the instance with one empty set and |
| 23 | solution size , which has no hitting set. Then the word map of `JitFlowShopStandard` writes |
| 24 | the standard word of the zoo instance of the construction. Its machine count is the solution |
| 25 | size plus one, or . |
| 26 | |
| 27 | **Theorem.** -Dominating-Set fpt-reduces to parameterized by the |
| 28 | number of machines , by a polynomial-time map with whose words have numbers at |
| 29 | most for their length. |
| 30 | |
| 31 | Since -Dominating-Set is W[2]-complete (lax-496464), is W[2]-hard |
| 32 | for , and strongly W[2]-hard: already on the words whose numbers are at most |
| 33 | . |
| 34 | |
| 35 | The reduction starts from Dominating Set and not from Hitting Set because the binary word of a |
| 36 | Hitting Set instance writes the universe size in binary, so the universe can be exponentially |
| 37 | larger than the word, while the construction has more than jobs. |
| 38 | -/ |
| 39 | |
| 40 | namespace Lax434175.JitFlowShopW2 |
| 41 | open 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)."} |
| 45 | axiom 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 |
| 48 | numbers at most a fixed power of the length of its output. -/ |
| 49 | axiom p315_r1_holds : ZooShopsResults.p315_r1 StandardReading.ops |
| 50 | |
| 51 | end Lax434175.JitFlowShopW2 |
| 52 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments