Lower Bounds for Problems Parameterized by Clique-width

on YouTube ↗25m

" summary

Claim: several classic problems (Dominating Set, Independent Set, Hamiltonian Cycle, Feedback Vertex Set) admit no algorithms of form 2^{o(k)}·n^{O(1)} when parameterized by clique-width unless ETH fails. Proof builds explicit labelled graph gadgets and composition reductions that encode SAT into graphs with clique-width Θ(k), giving concrete instance sizes and a matching lower bound; some reductions are tight against known algorithms so the impossibility is quantitative rather than merely qualitative.

AI-written summary · about

" chapters (10)

1. 0:00Start
2. 0:51Outline
3. 6:46Our results
4. 9:06Algorithmic upper bounds for Max-Cut
5. 10:48Capacitated Domination
6. 12:30Algorithmic lower bounds
7. 16:26Lower bound for Edge Dominating Set
8. 17:18The idea of reduction
9. 19:23Double parameterization
10. 21:31Open problems

" related talks

• 56mSatisfiability Algorithms IIMohan Paturi · Fine-Grained Complexity and Algorithm Design Boot Camp 2015
• 01h 07mSatisfiability Algorithms IMohan Paturi · Fine-Grained Complexity and Algorithm Design Boot Camp 2015
• 58mExponential-Time AlgorithmsThore Husfeldt · Fine-Grained Complexity and Algorithm Design Boot Camp 2015
• 01h 01mCircuit Complexity and Connections IIRyan Williams · Fine-Grained Complexity and Algorithm Design Boot Camp 2015
• 01h 07mComputational Complexity of Polynomial Time Problems: IntroductionVirginia Vassilevska Williams · Fine-Grained Complexity and Algorithm Design Boot Camp 2015
• 59mHardness for Graph Problems - Reductions Based on APSP and SETHVirginia Vassilevska Williams · Fine-Grained Complexity and Algorithm Design Boot Camp 2015
• 55mSparsification Lemma and ETHMohan Paturi · Fine-Grained Complexity and Algorithm Design Boot Camp 2015
• 35mSuperlinear Lower Bounds for Multipass Graph ProcessingKrzysztof Onak · Information Theory in Complexity Theory and Combinatorics 2015