Parameterized Reductions
summary
Covers parameterized reductions as a tool in parameterized complexity, explaining how reductions relate parameterized problems and are used to show hardness and algorithmic relationships. Discusses formal definitions, examples of reductions between problems, and how these reductions are applied in fine-grained complexity and algorithm design.
AI-written summary · about
chapters (17)
- 0:00Intro
- 0:38Lower bounds
- 1:28Parameterized complexity
- 6:05MULTICOLORED CLIQUE
- 10:05Variants of DOMINATING SET
- 11:02Regular graphs
- 12:19PARTIAL VERTEX COVER
- 14:32Basic hypotheses
- 23:28INDEPENDENT SET = Turing machines
- 28:37Summary
- 33:54Boolean circuit
- 34:22WEIGHTED CIRCUIT SATISFIABILITY
- 36:01Depth and weft
- 41:32Parameterized reductions
- 47:36LIST COLORING
- 49:39Vertex representation
- 58:53Vertex and edge representation
related talks
29mAn Isomorphism Between Parameterized Complexity and Classical Complexity, for both Time and Space
54mReduction theorems for effective parameterized verification of round- based distributed algorithms
01h 21mComputational Complexity in Theory and in Practice
15mProducts of Recursive Programs for Hypersafety Verification
25mSymbolic Bisimulation for Open and Parameterized Systems
21mMechanizing the CMP Abstraction for Parameterized Verification
23mTowards General and Tight Hardness Results for Graph Problems
31mParameterized Verification of Systems with Precise (0,1)-Counter Abstraction