Linear FPT reductions and computational lower bounds
From MaRDI portal
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; zbMATH DE number 139642
- 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
Cited in
(43)- On problems without polynomial kernels
- On recovering syntenic blocks from comparative maps
- A tighter bound for FFd algorithm
- Problems on finite automata and the exponential time hypothesis
- Algorithmic meta-theorems for restrictions of treewidth
- On the induced matching problem in Hamiltonian bipartite graphs
- On some FPT problems without polynomial Turing compressions
- Stable matchings with covering constraints: a complete computational trichotomy
- Constructing NP-intermediate problems by blowing holes with parameters of various properties
- Some lower bounds in parameterized \(\mathrm{AC}^{0}\)
- On the computational hardness based on linear fpt-reductions
- Tight lower bounds for certain parameterized NP-hard problems
- Parameterized computation and complexity: a new approach dealing with NP-hardness
- On hardness of approximating the parameterized clique problem
- On the independent set problem in random graphs
- Parameterized maximum path coloring
- What's next? Future directions in parameterized complexity
- On the variable hierarchy of first-order spectra
- Fixed-parameter tractability and lower bounds for stabbing problems
- An exponential time 2-approximation algorithm for bandwidth
- An exponential time 2-approximation algorithm for bandwidth
- Parameterized maximum path coloring
- 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
- Some lower bounds in parameterized \(\mathrm{AC}^0\)
- The constant inapproximability of the parameterized dominating set problem
- On finding the longest antisymmetric path in directed acyclic graphs
- The exponential time hypothesis and the parameterized clique problem
- A retrospective on genomic preprocessing for comparative genomics
- From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
- On Recovering Syntenic Blocks from Comparative Maps
- Computing and Combinatorics
- Slightly superexponential parameterized problems
- Parameterized algorithms for the happy set problem
- Communication and information complexity
- Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
- Pathfinding in self-deleting graphs
- There is no EPTAS for two-dimensional knapsack
- On miniaturized problems in parameterized complexity theory
- Parameterized dominating set problem in chordal graphs: Complexity and lower bound
- Strong computational lower bounds via parameterized complexity
- On product covering in 3-tier supply chain models: natural complete problems for W[3] and W[4]
- Efficient algorithms for clique problems
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)
