From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
From MaRDI portal
Publication:5115701
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)
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
Cites work
- scientific article; zbMATH DE number 1670809 (Why is no real title available?)
- scientific article; zbMATH DE number 1696630 (Why is no real title available?)
- scientific article; zbMATH DE number 6474898 (Why is no real title available?)
- scientific article; zbMATH DE number 5485536 (Why is no real title available?)
- scientific article; zbMATH DE number 7051292 (Why is no real title available?)
- A Greedy Heuristic for the Set-Covering Problem
- A Parallel Repetition Theorem
- A birthday repetition theorem and complexity of approximating dense CSPs
- A threshold of ln n for approximating set cover
- Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
- Analytical approach to parallel repetition
- Approximating Maximum Clique by Removing Subgraphs
- Approximation algorithms for label cover and the log-density threshold
- Approximations of Weighted Independent Set and Hereditary Subset Problems
- Better Inapproximability Results for MaxClique, Chromatic Number and Min-3Lin-Deletion
- Bicovering: covering edges with two small subsets of vertices
- Completely inapproximable monotone and antimonotone parameterized problems
- Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
- ETH hardness for densest-\(k\)-subgraph with perfect completeness
- Efficient probabilistically checkable proofs and applications to approximations
- Fixed-Parameter and Approximation Algorithms: A New Look
- Free Bits, PCPs, and Nonapproximability---Towards Tight Results
- Fundamentals of parameterized complexity
- Improved approximation algorithms for label cover problems
- Improved non-approximability results
- Inapproximability of maximum edge biclique, maximum balanced biclique and minimum \(k\)-cut from the small set expansion hypothesis
- Induced matchings
- Interactive proofs and the hardness of approximating cliques
- Linear FPT reductions and computational lower bounds
- Linear degree extractors and the inapproximability of max clique and chromatic number
- Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
- Lower bounds on the size of semidefinite programming relaxations
- NP-completeness of some generalizations of the maximum matching problem
- On Parameterized Approximability
- On Unapproximable Versions of $NP$-Complete Problems
- On a problem of K. Zarankiewicz
- On hardness of approximating the parameterized clique problem
- On the approximability of the maximum induced matching problem
- On the complexity of \(k\)-SAT
- On the complexity of approximating the independent set problem
- On the computational hardness based on linear fpt-reductions
- On the hardness of approximating minimization problems
- On the parameterized complexity of approximating dominating set
- On the possibility of faster \textsc{SAT} algorithms
- Parameterized Approximability of the Disjoint Cycle Problem
- Parameterized approximation of dominating set problems
- Polynomial integrality gaps for strong SDP relaxations of densest \(k\)-subgraph
- Probabilistic checking of proofs
- Proof verification and the hardness of approximation problems
- Relations between average case complexity and approximation complexity
- Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
- Simulating BPP using a general weak random source
- Some optimal inapproximability results
- Strong computational lower bounds via parameterized complexity
- The PCP theorem by gap amplification
- The approximation of maximum subgraph problems
- The dense \(k\)-subgraph problem
- The design of approximation algorithms
- The node-deletion problem for hereditary properties is NP-complete
- The parameterized complexity of \(k\)-biclique
- The parameterized complexity of the induced matching problem
- Time-approximation trade-offs for inapproximable problems
- Two-Prover Protocols---Low Error at Affordable Rates
- Which problems have strongly exponential complexity?
Cited in
(22)- On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic
- Exact and heuristic algorithms for the domination problem
- The inapproximability of \(k\)-dominatingSet for parameterized \(\mathsf{{AC}^0}\) circuits
- On the parameterized complexity of approximating dominating set
- On closest pair in Euclidean metric: monochromatic is as hard as bichromatic
- Computing densest \(k\)-subgraph with structural parameters
- Lossy kernels for connected dominating set on sparse graphs
- Parameterized approximation algorithms for bidirected Steiner network problems
- Parameterized approximation of dominating set problems
- Complexity of minimum-size arc-inconsistency explanations
- Parameterized inapproximability of independent set in \(H\)-free graphs
- Approximation and hardness of shift-bribery
- FPT Approximation for Constrained Metric k-Median/Means
- scientific article; zbMATH DE number 7561535 (Why is no real title available?)
- scientific article; zbMATH DE number 7650083 (Why is no real title available?)
- The exponential time hypothesis and the parameterized clique problem
- On hardness of approximating the parameterized clique problem
- On Geometric Set Cover for Orthants
- New tools and connections for exponential-time approximation
- Constant-Factor FPT Approximation for Capacitated k-Median
- A tight lower bound for planar Steiner orientation
- scientific article; zbMATH DE number 7559128 (Why is no real title available?)
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)
