Linear FPT reductions and computational lower bounds

DOI10.1145/1007352.1007391zbMath1192.68313OpenAlexW1987681136MaRDI QIDQ3580971

Xiuzhen Huang, Ge Xia, Iyad A. Kanj, Jian'er 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

Mathematics Subject Classification ID

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)

Related Items (32)

On miniaturized problems in parameterized complexity theory ⋮ Parameterized Maximum Path Coloring ⋮ Parameterized dominating set problem in chordal graphs: Complexity and lower bound ⋮ What’s Next? Future Directions in Parameterized Complexity ⋮ On product covering in 3-tier supply chain models: natural complete problems for W[3 and W[4]] ⋮ Problems on finite automata and the exponential time hypothesis ⋮ Fixed-parameter tractability and lower bounds for stabbing problems ⋮ An exponential time 2-approximation algorithm for bandwidth ⋮ Parameterized maximum path coloring ⋮ Some lower bounds in parameterized \(\mathrm{AC}^{0}\) ⋮ On the approximability of the exemplar adjacency number problem for genomes with gene repetitions ⋮ Parameterized complexity and inapproximability of dominating set problem in chordal and near chordal graphs ⋮ On the Variable Hierarchy of First-Order Spectra ⋮ Communication and information complexity ⋮ From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More ⋮ On finding the longest antisymmetric path in directed acyclic graphs ⋮ The Constant Inapproximability of the Parameterized Dominating Set Problem ⋮ Algorithmic meta-theorems for restrictions of treewidth ⋮ Parameterized algorithms for the happy set problem ⋮ Efficient algorithms for clique problems ⋮ On the computational hardness based on linear fpt-reductions ⋮ On the independent set problem in random graphs ⋮ On the induced matching problem in Hamiltonian bipartite graphs ⋮ Stable matchings with covering constraints: a complete computational trichotomy ⋮ There is no EPTAS for two-dimensional knapsack ⋮ On problems without polynomial kernels ⋮ A Retrospective on Genomic Preprocessing for Comparative Genomics ⋮ An Exponential Time 2-Approximation Algorithm for Bandwidth ⋮ On recovering syntenic blocks from comparative maps ⋮ On Recovering Syntenic Blocks from Comparative Maps ⋮ Parameterized computation and complexity: a new approach dealing with NP-hardness ⋮ Constructing NP-intermediate problems by blowing holes with parameters of various properties

This page was built for publication: Linear FPT reductions and computational lower bounds