Lower bounds based on the exponential time hypothesis
From MaRDI portal
Recommendations
- The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems
- On problems as hard as CNF-SAT
- Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
- On some fine-grained questions in algorithms and complexity
- The exponential time hypothesis and the parameterized clique problem
Cited in
(only showing first 100 items - show all)- On residual approximation in solution extension problems
- On the optimality of exact and approximation algorithms for scheduling problems
- Scaffolding problems revisited: complexity, approximation and fixed parameter tractable algorithms, and some special cases
- Problems on finite automata and the exponential time hypothesis
- Improved FPT algorithms for weighted independent set in bull-free graphs
- Sparsification and subexponential approximation
- The P3 infection time is W[1]-hard parameterized by the treewidth
- Cliques enumeration and tree-like resolution proofs
- Complexity and lowers bounds for power edge set problem
- Exact algorithms for finding well-connected 2-clubs in sparse real-world graphs: theory and experiments
- Subexponential-time algorithms for maximum independent set in \(P_t\)-free and broom-free graphs
- Explicit linear kernels for packing problems
- Coloring invariants of knots and links are often intractable
- Pattern matching and consensus problems on weighted sequences and profiles
- Temporal vertex cover with a sliding time window
- On the size of partial derivatives and the word membership problem
- Metric dimension parameterized by treewidth
- On the parametrized complexity of read-once refutations in UTVPI+ constraint systems
- Hitting forbidden induced subgraphs on bounded treewidth graphs
- Fine-grained complexity of rainbow coloring and its variants
- Defensive alliances in graphs
- On minimizing regular expressions without Kleene star
- Complexity and approximation results on the shared transportation problem
- Finding optimal triangulations parameterized by edge clique cover
- Learning from positive and negative examples: dichotomies and parameterized algorithms
- On the complexity of detecting hazards
- Complexity and inapproximability results for balanced connected subgraph problem
- The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems
- Acyclic orders, partition schemes and CSPs: unified hardness proofs and improved algorithms
- A multi-parameter analysis of hard problems on deterministic finite automata
- Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms
- Routing with congestion in acyclic digraphs
- Complexity of independency and cliquy trees
- Hitting minors on bounded treewidth graphs. III. Lower bounds
- Minimum fill-in: inapproximability and almost tight lower bounds
- Hitting minors on bounded treewidth graphs. II. Single-exponential algorithms
- Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression
- Fixed-parameter complexity and approximability of norm maximization
- An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems
- A complexity and approximation framework for the maximization scaffolding problem
- Characterization and complexity results on jumping finite automata
- Inferring local transition functions of discrete dynamical systems from observations of system behavior
- Solving Hamiltonian cycle by an EPT algorithm for a non-sparse parameter
- A tight lower bound for vertex planarization on graphs of bounded treewidth
- Hitting forbidden subgraphs in graphs of bounded treewidth
- Linear kernels for outbranching problems in sparse digraphs
- On the complexity of restoring corrupted colorings
- Local search for string problems: brute-force is essentially optimal
- Faster algorithms for vertex partitioning problems parameterized by clique-width
- Tight bounds for parameterized complexity of cluster editing with a small number of clusters
- Algorithms and almost tight results for 3-colorability of small diameter graphs
- Finding a maximum minimal separator: graph classes and fixed-parameter tractability
- A multistage view on 2-satisfiability
- On the d-claw vertex deletion problem
- Grundy Coloring and friends, half-graphs, bicliques
- Problems on finite automata and the exponential time hypothesis
- Efficiently approximating color-spanning balls
- Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis
- A dichotomy result for Ramsey quantifiers
- Planar Digraphs
- On the parameterised complexity of string morphism problems
- Strong partial clones and the time complexity of SAT problems
- The parameterised complexity of list problems on graphs of bounded treewidth
- Lower bounds for the graph homomorphism problem
- scientific article; zbMATH DE number 6520244 (Why is no real title available?)
- On the complexity of scaffolding problems: from cliques to sparse graphs
- scientific article; zbMATH DE number 3938347 (Why is no real title available?)
- The parameterized complexity of local search for TSP, more refined
- Tight complexity bounds for FPT subgraph problems parameterized by the clique-width
- Fractals for kernelization lower bounds
- On lower bounds for the time of computation
- A fast and simple subexponential fixed parameter algorithm for one-sided crossing minimization
- On feedback vertex set: new measure and new structures
- Coverability and sub-exponential parameterized algorithms in planar graphs
- Coloring Graphs with Constraints on Connectivity
- scientific article; zbMATH DE number 7378390 (Why is no real title available?)
- Dual parameterization of weighted coloring
- Refining complexity analyses in planning by exploiting the exponential time hypothesis
- Counting Small Induced Subgraphs Satisfying Monotone Properties
- Almost tight lower bounds for hard cutting problems in embedded graphs
- Hitting forbidden induced subgraphs on bounded treewidth graphs
- Fine-Grained Complexity Theory (Tutorial)
- Fine-Grained Complexity of Rainbow Coloring and its Variants.
- scientific article; zbMATH DE number 7204396 (Why is no real title available?)
- Subexponential parameterized algorithms for graphs of polynomial growth
- Optimal algorithms for hitting (topological) minors on graphs of bounded treewidth
- scientific article; zbMATH DE number 7236415 (Why is no real title available?)
- Lower bounds for dynamic programming on planar graphs of bounded cutwidth
- Orthogonal vectors indexing
- Characterizing polynomial Ramsey quantifiers
- Preventing unraveling in social networks: the anchored \(k\)-core problem
- Fine-grained complexity of the graph homomorphism problem for bounded-treewidth graphs
- scientific article; zbMATH DE number 7651154 (Why is no real title available?)
- Bounding the running time of algorithms for scheduling and packing problems
- Strong triadic closure in cographs and graphs of low maximum degree
- Recognizing \(k\)-clique extendible orderings
- Quasipolynomiality of the Smallest Missing Induced Subgraph
- A note on hardness of computing recursive teaching dimension
- The 2CNF Boolean formula satisfiability problem and the linear space hypothesis
- What Is Known About Vertex Cover Kernelization?
This page was built for publication: Lower bounds based on the exponential time hypothesis
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4904144)
