Parameterized Inapproximability of Max k-Subset Intersection under ETH
Talkat Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms · on Friday, 2015-11-06·
summary
Proves an FPT gap-producing reduction from k‑Clique to Max k‑Subset Intersection that maps a k input to a bipartite H with s = k^2 so that a k‑clique yields s left vertices with exponentially many common neighbors while no clique gives only tiny intersection; derives ETH‑based runtime lower bounds of roughly n^{Ω(√k)} hardness under ETH for any f(k)·poly(n) approximation, using a derandomized combinatorial construction for the extractor graph.
AI-written summary · about
chapters (15)
- 0:00Start
- 2:32Previous work
- 3:19Difficulty of showing parameterized inapproximability
- 3:58A gap-producing reduction
- 5:31Consequence under ETH
- 6:48Trade-off between running time and approximation ratio
- 7:36Trade-off between running-time and approximation ratio
- 8:30Inapproacimability of other natural parameterized problem
- 8:59From MAX-K-SUBSET-INTERSECTION to k-CLIQUE?
- 12:58Constant inapproximability of dominating set
- 15:32Previous inapproximability results of dominating set
- 18:46Proof of the gap-producing reduction
- 22:13Probabilistic construction of T
- 23:10Derandomizing the reduction
- 24:30Summary
related talks
34mTesting Intersectingness of Uniform Families or how Dana and I intersected
25mAn Improved Lower Bound for Matroid Intersection Prophet inequalities
55mSiegel's Theorem, Edge Coloring, and a Holant Dichotomy
01h 32mInapproximability of Constraint Satisfaction Problems I
A Formal Disproof of Hirsch Conjecture
28mSettling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
25mOn computing homological hitting sets
25mExponential separations using guarded extension variables