From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More

DOI10.1137/18M1166869zbMath1452.68083WikidataQ115525600 ScholiaQ115525600MaRDI QIDQ5115701

Marek Cygan, Parinya Chalermsook, Luca Trevisan, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, Guy Kortsarz

Publication date: 18 August 2020

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

cliquedominating sethardness of approximationparameterized complexitysubexponential-time algorithmsfine-grained complexity

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (16)

Computing densest \(k\)-subgraph with structural parameters ⋮ Complexity of minimum-size arc-inconsistency explanations ⋮ Unnamed Item ⋮ On closest pair in Euclidean metric: monochromatic is as hard as bichromatic ⋮ Approximation and hardness of shift-Bribery ⋮ FPT Approximation for Constrained Metric k-Median/Means ⋮ A tight lower bound for planar Steiner orientation ⋮ New tools and connections for exponential-time approximation ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Constant-Factor FPT Approximation for Capacitated k-Median ⋮ On Geometric Set Cover for Orthants ⋮ Parameterized inapproximability of independent set in \(H\)-free graphs ⋮ On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic ⋮ Lossy Kernels for Connected Dominating Set on Sparse Graphs ⋮ Parameterized Approximation Algorithms for Bidirected Steiner Network Problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Improved approximation algorithms for label cover problems
• Strong computational lower bounds via parameterized complexity
• Parameterized approximation of dominating set problems
• The parameterized complexity of the induced matching problem
• The node-deletion problem for hereditary properties is NP-complete
• NP-completeness of some generalizations of the maximum matching problem
• On the complexity of approximating the independent set problem
• Induced matchings
• Which problems have strongly exponential complexity?
• On the approximability of the maximum induced matching problem
• Simulating BPP using a general weak random source
• Completely inapproximable monotone and antimonotone parameterized problems
• On subexponential and FPT-time inapproximability
• On the computational hardness based on linear fpt-reductions
• On Hardness of Approximating the Parameterized Clique Problem
• Improved non-approximability results
• Fixed-Parameter and Approximation Algorithms: A New Look
• Detecting high log-densities
• Lower Bounds on the Size of Semidefinite Programming Relaxations
• The Design of Approximation Algorithms
• Proof verification and the hardness of approximation problems
• A threshold of ln n for approximating set cover
• On Parameterized Approximability
• Relations between average case complexity and approximation complexity
• Linear FPT reductions and computational lower bounds
• Better Inapproximability Results for MaxClique, Chromatic Number and Min-3Lin-Deletion
• Probabilistic checking of proofs
• A Greedy Heuristic for the Set-Covering Problem
• On the hardness of approximating minimization problems
• Interactive proofs and the hardness of approximating cliques
• A Parallel Repetition Theorem
• Free Bits, PCPs, and Nonapproximability---Towards Tight Results
• Approximations of Weighted Independent Set and Hereditary Subset Problems
• Two-Prover Protocols---Low Error at Affordable Rates
• Approximation Algorithms for Label Cover and The Log-Density Threshold
• ETH Hardness for Densest-k-Subgraph with Perfect Completeness
• Bicovering: Covering edges with two small subsets of vertices
• The approximation of maximum subgraph problems
• Approximating Maximum Clique by Removing Subgraphs
• Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
• Inapproximability of Maximum Edge Biclique, Maximum Balanced Biclique and Minimum k-Cut from the Small Set Expansion Hypothesis
• On the parameterized complexity of approximating dominating set
• Efficient probabilistically checkable proofs and applications to approximations
• Analytical approach to parallel repetition
• The Parameterized Complexity of k-B<scp>iclique</scp>
• Coloring Graph Powers: Graph Product Bounds and Hardness of Approximation
• Parameterized Approximability of the Disjoint Cycle Problem
• Some optimal inapproximability results
• On Unapproximable Versions of $NP$-Complete Problems
• Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
• On a problem of K. Zarankiewicz
• The PCP theorem by gap amplification
• The dense \(k\)-subgraph problem
• Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
• On the complexity of \(k\)-SAT

This page was built for publication: From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More