From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
From MaRDI portal
Publication:5115701
DOI10.1137/18M1166869zbMATH Open1452.68083WikidataQ115525600 ScholiaQ115525600MaRDI QIDQ5115701FDOQ5115701
Authors: Parinya Chalermsook, Marek Cygan, B. Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, Luca Trevisan, Guy Kortsarz 
Publication date: 18 August 2020
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Recommendations
- Fixed-Parameter and Approximation Algorithms: A New Look
- On the parameterized complexity of approximating dominating set
- On the Parameterized Complexity of Approximating Dominating Set
- On hardness of approximating the parameterized clique problem
- The exponential time hypothesis and the parameterized clique problem
dominating setcliqueparameterized complexityhardness of approximationsubexponential-time algorithmsfine-grained complexity
Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Parameterized complexity, tractability and kernelization (68Q27)
Cites Work
- A threshold of ln n for approximating set cover
- Fundamentals of parameterized complexity
- The design of approximation algorithms
- Relations between average case complexity and approximation complexity
- Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
- A Greedy Heuristic for the Set-Covering Problem
- The node-deletion problem for hereditary properties is NP-complete
- Which problems have strongly exponential complexity?
- Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
- Linear degree extractors and the inapproximability of max clique and chromatic number
- Proof verification and the hardness of approximation problems
- Probabilistic checking of proofs
- Interactive proofs and the hardness of approximating cliques
- Approximating Maximum Clique by Removing Subgraphs
- Title not available (Why is that?)
- Some optimal inapproximability results
- The dense \(k\)-subgraph problem
- On the complexity of \(k\)-SAT
- The Parameterized Complexity of k-B<scp>iclique</scp>
- On Unapproximable Versions of $NP$-Complete Problems
- On a problem of K. Zarankiewicz
- Induced matchings
- Title not available (Why is that?)
- Improved non-approximability results
- On the hardness of approximating minimization problems
- Coloring Graph Powers: Graph Product Bounds and Hardness of Approximation
- On the complexity of approximating the independent set problem
- Simulating BPP using a general weak random source
- Approximations of Weighted Independent Set and Hereditary Subset Problems
- Strong computational lower bounds via parameterized complexity
- The parameterized complexity of the induced matching problem
- A Parallel Repetition Theorem
- Efficient probabilistically checkable proofs and applications to approximations
- Analytical approach to parallel repetition
- NP-completeness of some generalizations of the maximum matching problem
- On the approximability of the maximum induced matching problem
- Title not available (Why is that?)
- Lower Bounds on the Size of Semidefinite Programming Relaxations
- Linear FPT reductions and computational lower bounds
- The approximation of maximum subgraph problems
- Title not available (Why is that?)
- On the computational hardness based on linear fpt-reductions
- On Parameterized Approximability
- Better Inapproximability Results for MaxClique, Chromatic Number and Min-3Lin-Deletion
- Parameterized approximation of dominating set problems
- On the parameterized complexity of approximating dominating set
- Free Bits, PCPs, and Nonapproximability---Towards Tight Results
- The PCP theorem by gap amplification
- Parameterized Approximability of the Disjoint Cycle Problem
- Improved approximation algorithms for label cover problems
- Completely inapproximable monotone and antimonotone parameterized problems
- On hardness of approximating the parameterized clique problem
- Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
- Title not available (Why is that?)
- On subexponential and FPT-time inapproximability
- Two-Prover Protocols---Low Error at Affordable Rates
- Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
- Title not available (Why is that?)
- Fixed-Parameter and Approximation Algorithms: A New Look
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Bicovering: Covering edges with two small subsets of vertices
- Inapproximability of Maximum Edge Biclique, Maximum Balanced Biclique and Minimum k-Cut from the Small Set Expansion Hypothesis
- Approximation Algorithms for Label Cover and The Log-Density Threshold
- ETH Hardness for Densest-k-Subgraph with Perfect Completeness
Cited In (19)
- Exact and heuristic algorithms for the domination problem
- On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic
- The inapproximability of \(k\)-dominatingSet for parameterized \(\mathsf{{AC}^0}\) circuits
- On closest pair in Euclidean metric: monochromatic is as hard as bichromatic
- Computing densest \(k\)-subgraph with structural parameters
- Parameterized approximation of dominating set problems
- Complexity of minimum-size arc-inconsistency explanations
- Parameterized inapproximability of independent set in \(H\)-free graphs
- Lossy Kernels for Connected Dominating Set on Sparse Graphs
- Approximation and hardness of shift-Bribery
- FPT Approximation for Constrained Metric k-Median/Means
- Title not available (Why is that?)
- Title not available (Why is that?)
- On Geometric Set Cover for Orthants
- Constant-Factor FPT Approximation for Capacitated k-Median
- New tools and connections for exponential-time approximation
- Parameterized Approximation Algorithms for Bidirected Steiner Network Problems
- A tight lower bound for planar Steiner orientation
- Title not available (Why is that?)
This page was built for publication: From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5115701)
