Strong computational lower bounds via parameterized complexity
From MaRDI portal
Recommendations
Cites work
- scientific article; zbMATH DE number 3910446 (Why is no real title available?)
- scientific article; zbMATH DE number 1304341 (Why is no real title available?)
- scientific article; zbMATH DE number 1305487 (Why is no real title available?)
- scientific article; zbMATH DE number 1330033 (Why is no real title available?)
- scientific article; zbMATH DE number 1332665 (Why is no real title available?)
- scientific article; zbMATH DE number 1161563 (Why is no real title available?)
- scientific article; zbMATH DE number 2086667 (Why is no real title available?)
- Algorithms for maximum independent sets
- An O(20.304n) Algorithm for Solving Maximum Independent Set Problem
- Characterizing parallel hierarchies by reducibilities
- Finding a Maximum Independent Set
- Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
- Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
- Fundamentals of Computation Theory
- Genetic Design of Drugs Without Side-Effects
- Matrix multiplication via arithmetic progressions
- On limited nondeterminism and the complexity of the V-C dimension
- On the complexity of database queries
- Optimization, approximation, and complexity classes
- Solving large FPT problems on coarse-grained parallel machines
- Tight lower bounds for certain parameterized NP-hard problems
- Vertex cover: Further observations and further improvements
- Vertex packings: Structural properties and algorithms
- Which problems have strongly exponential complexity?
Cited in
(89)- Tight lower bounds for certain parameterized NP-hard problems
- Twin-width and polynomial kernels
- On the Fine Grained Complexity of Finite Automata Non-emptiness of Intersection
- On the pseudo-achromatic number problem
- Lower bounds for the graph homomorphism problem
- Tight complexity bounds for FPT subgraph problems parameterized by clique-width
- Genus characterizes the complexity of certain graph problems: Some tight results
- A second step toward the strong polynomial-time hierarchy
- Subset feedback vertex set on graphs of bounded independent set size
- Parameterized Algorithms for Power-Efficiently Connecting Wireless Sensor Networks: Theory and Experiments
- On the Pseudo-achromatic Number Problem
- If the current clique algorithms are optimal, so is Valiant's parser
- Grundy Coloring and friends, half-graphs, bicliques
- The complexity of dependency detection and discovery in relational databases
- Resolving conflicts for lower-bounded clustering
- Computing vertex-surjective homomorphisms to partially reflexive trees
- A multistage view on 2-satisfiability
- A dichotomy result for Ramsey quantifiers
- Parameterized complexity of computing maximum minimal blocking and hitting sets
- Parameterized and subexponential-time complexity of satisfiability problems and applications
- Efficiently enumerating hitting sets of hypergraphs arising in data profiling
- Parameterized and subexponential-time complexity of satisfiability problems and applications
- Counting induced subgraphs: a topological approach to \#W[1]-hardness
- Kernelization: new upper and lower bound techniques
- Parameterized counting of partially injective homomorphisms
- Can Romeo and Juliet meet? Or rendezvous games with adversaries on graphs
- From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
- Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity
- Computing vertex-surjective homomorphisms to partially reflexive trees
- On the Complexity of Bounded Context Switching.
- On first-order definitions of subgraph isomorphism properties
- From the \(W\)-hierarchy to XNLP. Classes of fixed parameter intractability
- On parameterized exponential time complexity
- Faster algorithms for counting subgraphs in sparse graphs
- The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs
- Parameterized complexity of firefighting
- scientific article; zbMATH DE number 7204413 (Why is no real title available?)
- Strong co-nondeterministic lower bounds for NP cannot be proved feasibly
- Tight complexity bounds for FPT subgraph problems parameterized by the clique-width
- Finding small satisfying assignments faster than brute force: a fine-grained perspective into boolean constraint satisfaction
- Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation
- Some lower bounds in parameterized \(\mathrm{AC}^{0}\)
- A Tight Algorithm for Strongly Connected Steiner Subgraph on Two Terminals with Demands (Extended Abstract)
- Counting induced subgraphs: an algebraic approach to \#W[1]-hardness
- On the complexity of connection games
- On the independent set problem in random graphs
- The union of minimal hitting sets: parameterized combinatorial bounds and counting
- Calculation of discrepancy measures and applications
- Counting Small Induced Subgraphs Satisfying Monotone Properties
- Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation
- On the first-order complexity of induced subgraph isomorphism
- Parameterized Counting and Cayley Graph Expanders
- Some lower bounds in parameterized \(\mathrm{AC}^0\)
- Parameterized complexity and subexponential-time computability
- Distance-based clique relaxations in networks: \(s\)-clique and \(s\)-club
- An initial study of time complexity in infinite-domain constraint satisfaction
- Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions)
- Strong time bounds: Non-computable bounds and a hierarchy theorem
- A tight algorithm for strongly connected Steiner subgraph on two terminals with demands
- On the complexity of computing the \(k\)-restricted edge-connectivity of a graph
- Refining complexity analyses in planning by exploiting the exponential time hypothesis
- Half-integrality, LP-branching, and FPT algorithms
- A spectral algorithm for finding maximum cliques in dense random intersection graphs
- Counting induced subgraphs: a topological approach to \#W[1]-hardness
- An improved lower bound on approximation algorithms for the closest substring problem
- Fine-Grained Reductions and Quantum Speedups for Dynamic Programming.
- Safe approximation and its relation to kernelization
- On the variable hierarchy of first-order spectra
- Computing the depth distribution of a set of boxes
- A tight lower bound for planar Steiner orientation
- Maximum locally irregular induced subgraphs via minimum irregulators
- Characterizing polynomial Ramsey quantifiers
- Deciding Parity Games in Quasi-polynomial Time
- Using a Geometric Lens to Find \(\boldsymbol{k}\)-Disjoint Shortest Paths
- Counting induced subgraphs: an algebraic approach to \#W[1]-hardness
- The complexity of pattern counting in directed graphs, parameterised by the outdegree
- Pattern masking for dictionary matching: theory and practice
- Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
- Backdoor sets for CSP
- Lacon-, Shrub- and Parity-Decompositions: Characterizing Transductions of Bounded Expansion Classes
- Logical complexity of induced subgraph isomorphism for certain families of graphs
- Tight FPT approximation for constrained \(k\)-center and \(k\)-supplier
- Counting Small Induced Subgraphs with Hereditary Properties
- Parameterised and fine-grained subgraph counting, modulo 2
- Sum-of-Products with Default Values: Algorithms and Complexity Results
- Counting subgraphs in somewhere dense graphs
- Iterated lower bound formulas: a diagonalization-based approach to proof complexity
- Obtaining a proportional allocation by deleting items
- Quasipolynomiality of the Smallest Missing Induced Subgraph
This page was built for publication: Strong computational lower bounds via parameterized complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q856413)
