Linear FPT reductions and computational lower bounds
From MaRDI portal
Publication:3580971
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
(42)- An exponential time 2-approximation algorithm for bandwidth
- Parameterized maximum path coloring
- Some lower bounds in parameterized \(\mathrm{AC}^0\)
- An exponential time 2-approximation algorithm for bandwidth
- Parameterized algorithms for the happy set problem
- 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 independent set problem in random graphs
- Constructing NP-intermediate problems by blowing holes with parameters of various properties
- From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
- What's next? Future directions in parameterized complexity
- 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
- On problems without polynomial kernels
- A tighter bound for FFd algorithm
- On miniaturized problems in parameterized complexity theory
- Slightly superexponential parameterized problems
- Stable matchings with covering constraints: a complete computational trichotomy
- Algorithmic meta-theorems for restrictions of treewidth
- A retrospective on genomic preprocessing for comparative genomics
- 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
- Strong computational lower bounds via parameterized complexity
- Problems on finite automata and the exponential time hypothesis
- Parameterized maximum path coloring
- 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 finding the longest antisymmetric path in directed acyclic graphs
- The exponential time hypothesis and the parameterized clique problem
- On Recovering Syntenic Blocks from Comparative Maps
- Communication and information complexity
- On hardness of approximating the parameterized clique problem
- The constant inapproximability of the parameterized dominating set problem
- There is no EPTAS for two-dimensional knapsack
- Fixed-parameter tractability and lower bounds for stabbing problems
- On some FPT problems without polynomial Turing compressions
- Some lower bounds in parameterized \(\mathrm{AC}^{0}\)
- On the variable hierarchy of first-order spectra
- On the induced matching problem in Hamiltonian bipartite graphs
- Computing and Combinatorics
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)
