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)- A parameterized complexity view on collapsing \(k\)-cores
- A multistage view on 2-satisfiability
- Coverability and sub-exponential parameterized algorithms in planar graphs
- Local search for string problems: brute-force is essentially optimal
- Algorithms and almost tight results for 3-colorability of small diameter graphs
- Algorithmic analysis of priority-based bin packing
- Grundy Coloring and friends, half-graphs, bicliques
- A dichotomy result for Ramsey quantifiers
- Induced tree covering and the generalized Yutsis property
- Bounding the running time of algorithms for scheduling and packing problems
- Hardness of interval scheduling on unrelated machines
- Exact exponential algorithms for clustering problems
- Enumerating minimal connected dominating sets
- The complexity of strong conflict-free vertex-connection k-colorability
- Cluster editing with locally bounded modifications
- Characterizing polynomial Ramsey quantifiers
- Hitting minors on bounded treewidth graphs. III. Lower bounds
- Pattern matching and consensus problems on weighted sequences and profiles
- Improved FPT algorithms for weighted independent set in bull-free graphs
- The fine-grained complexity of graph homomorphism parameterized by clique-width
- Fixed-parameter complexity and approximability of norm maximization
- The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems
- Enumerating minimal connected dominating sets
- Efficiently approximating color-spanning balls
- Strong triadic closure in cographs and graphs of low maximum degree
- Temporal vertex cover with a sliding time window
- Complexity and inapproximability results for balanced connected subgraph problem
- Computing Hamiltonian paths with partial order restrictions
- Preventing unraveling in social networks: the anchored \(k\)-core problem
- On residual approximation in solution extension problems
- Optimal algorithms for hitting (topological) minors on graphs of bounded treewidth
- Acyclic orders, partition schemes and CSPs: unified hardness proofs and improved algorithms
- Counting Small Induced Subgraphs Satisfying Monotone Properties
- Complexity of token swapping and its variants
- scientific article; zbMATH DE number 7651154 (Why is no real title available?)
- Faster algorithms for vertex partitioning problems parameterized by clique-width
- Scaffolding problems revisited: complexity, approximation and fixed parameter tractable algorithms, and some special cases
- Orthogonal vectors indexing
- On the complexity of scaffolding problems: from cliques to sparse graphs
- Counting homomorphisms in plain exponential time
- Fine-grained complexity of the graph homomorphism problem for bounded-treewidth graphs
- Quasipolynomiality of the Smallest Missing Induced Subgraph
- Coloring Graphs with Constraints on Connectivity
- Inferring local transition functions of discrete dynamical systems from observations of system behavior
- Subsequences in bounded ranges: matching and analysis problems
- On minimizing regular expressions without Kleene star
- Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis
- Complexity and lowers bounds for power edge set problem
- Planar Digraphs
- Refined lower bounds for nearest neighbor condensation
- On exponential-time hypotheses, derandomization, and circuit lower bounds
- On lower bounds for the time of computation
- On the parameterised complexity of string morphism problems
- Subexponential parameterized algorithms for graphs of polynomial growth
- Dual parameterization of weighted coloring
- Almost tight lower bounds for hard cutting problems in embedded graphs
- scientific article; zbMATH DE number 7204396 (Why is no real title available?)
- Complexity and approximation results on the shared transportation problem
- On the shared transportation problem: computational hardness and exact approach
- scientific article; zbMATH DE number 7378390 (Why is no real title available?)
- Parameterized complexity of modular dominating structures in bounded-treewidth graphs
- Dual parameterization of weighted coloring
- The strongish planted clique hypothesis and its consequences
- Offensive alliances in signed graphs
- Priority-based bin packing with subset constraints
- Defensive alliances in graphs
- scientific article; zbMATH DE number 3938347 (Why is no real title available?)
- \(b\)-coloring parameterized by clique-width
- Concerning infeasibility of the wave functions of the universe
- Lower bounds for the graph homomorphism problem
- A complexity and approximation framework for the maximization scaffolding problem
- Color-constrained arborescences in edge-colored digraphs
- Graph search trees and the Intermezzo problem
- 4 vs 7 sparse undirected unweighted diameter is SETH-hard at time \(n^{4/3}\)
- Problems on finite automata and the exponential time hypothesis
- Degrees and gaps: tight complexity results of general factor problems parameterized by treewidth and cutwidth
- On the size of partial derivatives and the word membership problem
- Metric dimension parameterized by treewidth
- Problems on finite automata and the exponential time hypothesis
- Tight bounds for parameterized complexity of cluster editing with a small number of clusters
- What Is Known About Vertex Cover Kernelization?
- Minimum fill-in: inapproximability and almost tight lower bounds
- A note on hardness of computing recursive teaching dimension
- On the parametrized complexity of read-once refutations in UTVPI+ constraint systems
- Finding optimal triangulations parameterized by edge clique cover
- Algorithms solving the matching cut problem
- Finding a maximum minimal separator: graph classes and fixed-parameter tractability
- Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms
- Fine-Grained Complexity of Rainbow Coloring and its Variants.
- Hitting forbidden subgraphs in graphs of bounded treewidth
- Coloring invariants of knots and links are often intractable
- Parameterized complexity of path set packing
- The 2CNF Boolean formula satisfiability problem and the linear space hypothesis
- Strong partial clones and the time complexity of SAT problems
- Recognizing \(k\)-clique extendible orderings
- Polynomial formulations as a barrier for reduction-based hardness proofs
- The parameterised complexity of list problems on graphs of bounded treewidth
- Offensive alliances in signed graphs
- A multi-parameter analysis of hard problems on deterministic finite automata
- Towards tight bounds for the graph homomorphism problem parameterized by cutwidth via asymptotic matrix parameters
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)
