Linear FPT reductions and computational lower bounds
DOI10.1145/1007352.1007391zbMATH Open1192.68313OpenAlexW1987681136MaRDI QIDQ3580971FDOQ3580971
Xiuzhen Huang, Ge Xia, Iyad Kanj, Jianer Chen
Publication date: 15 August 2010
Published in: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1007352.1007391
Recommendations
- On the computational hardness based on linear fpt-reductions
- scientific article; zbMATH DE number 1351079
- Publication:4886070
- Complexity Lower Bounds using Linear Algebra
- Computing and Combinatorics
- scientific article
- On the complexity of linear programming under finite precision arithmetic
- Lower bounds for parallel linear programming and other problems
- Lower bounds for the complexity of linear functionals in the randomized setting
- Half-integrality, LP-branching, and FPT algorithms
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cited In (36)
- An exponential time 2-approximation algorithm for bandwidth
- Parameterized maximum path coloring
- Parameterized algorithms for the happy set problem
- On the approximability of the exemplar adjacency number problem for genomes with gene repetitions
- Parameterized Maximum Path Coloring
- What’s Next? Future Directions in Parameterized Complexity
- Parameterized complexity and inapproximability of dominating set problem in chordal and near chordal graphs
- On the independent set problem in random graphs
- On the Variable Hierarchy of First-Order Spectra
- Constructing NP-intermediate problems by blowing holes with parameters of various properties
- Tight lower bounds for certain parameterized NP-hard problems
- Efficient algorithms for clique problems
- Parameterized dominating set problem in chordal graphs: Complexity and lower bound
- The Constant Inapproximability of the Parameterized Dominating Set Problem
- On problems without polynomial kernels
- A tighter bound for FFd algorithm
- On miniaturized problems in parameterized complexity theory
- Stable matchings with covering constraints: a complete computational trichotomy
- Algorithmic meta-theorems for restrictions of treewidth
- On recovering syntenic blocks from comparative maps
- On the computational hardness based on linear fpt-reductions
- Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
- Problems on finite automata and the exponential time hypothesis
- On product covering in 3-tier supply chain models: natural complete problems for W[3] and W[4]
- Parameterized computation and complexity: a new approach dealing with NP-hardness
- On Recovering Syntenic Blocks from Comparative Maps
- On finding the longest antisymmetric path in directed acyclic graphs
- Communication and information complexity
- An Exponential Time 2-Approximation Algorithm for Bandwidth
- There is no EPTAS for two-dimensional knapsack
- From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More
- Fixed-parameter tractability and lower bounds for stabbing problems
- Some lower bounds in parameterized \(\mathrm{AC}^{0}\)
- On the induced matching problem in Hamiltonian bipartite graphs
- Computing and Combinatorics
- A Retrospective on Genomic Preprocessing for Comparative Genomics
This page was built for publication: Linear FPT reductions and computational lower bounds
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3580971)
