Which Problems Have Strongly Exponential Complexity?

2001/12/01 by Russell Impagliazzo, Ramamohan Paturi, Francis Zane · 1,364 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics #Complexity and Algorithms in Graphs #Complexity class #Discrete mathematics #Exponential function #Machine Learning and Algorithms #Mathematics #Time complexity #Upper and lower bounds

paper · doi:10.1006/jcss.2001.1774

published in Journal of Computer and System Sciences 63(4), 512-530 (Elsevier BV)

openalex publication_date 2001/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/23

Cited by

• Revenue maximization in Stackelberg Pricing Games: beyond the combinatorial setting
• PCP Theorems, SETH and More: Towards Proving Sub-linear Time Inapproximability
• The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise
• Towards Tight Approximation Bounds for Graph Diameter and Eccentricities
• On the Complexity Landscape of Connected f -Factor Problems
• Knapsack Problems: A Parameterized Point of View
• On the Fine-grained Complexity of One-Dimensional Dynamic Programming
• Polynomial Kernels for Weighted Problems
• Lossy Kernelization
• CSPs with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations
• Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless SETH fails
• Inapproximability of Maximum Biclique Problems, Minimum k-Cut and Densest At-Least-k-Subgraph from the Small Set Expansion Hypothesis
• Hardness of Approximate Nearest Neighbor Search under L-infinity
• A Proof Checking View of Parameterized Complexity
• On Fine-Grained Exact Computation in Regular Graphs
• Detecting communities is hard, and counting them is even harder
• On the Computational Complexity of MapReduce
• On Structural Parameterizations of Hitting Set: Hitting Paths in Graphs Using 2-SAT
• Subexponential-time Algorithms for Maximum Independent Set in P_t-free and Broom-free Graphs
• Into the Square - On the Complexity of Quadratic-Time Solvable Problems
• Parameterized Complexity of Bandwidth on Trees
• On the Parameterized Complexity and Kernelization of the Workflow Satisfiability Problem
• Popular conjectures imply strong lower bounds for dynamic problems
• Dynamic Programming for Graphs on Surfaces
• Lower Bounds for QBFs of Bounded Treewidth
• A New Direction for Counting Perfect Matchings
• The Relative Exponential Time Complexity of Approximate Counting Satisfying Assignments
• A randomized polynomial kernelization for Vertex Cover with a smaller parameter
• Subexponential and FPT-time Inapproximability of Independent Set and Related Problems
• Multivariate Complexity Analysis of Geometric \sc Red Blue Set Cover
• Quadratic-Time Hardness of LCS and other Sequence Similarity Measures
• Kernels for (connected) Dominating Set on graphs with Excluded Topological subgraphs
• On the complexity of detecting hazards
• Circuit Depth Reductions
• Half-integrality, LP-branching and FPT Algorithms
• Simultaneous Feedback Vertex Set: A Parameterized Perspective
• Improved Lower Bounds for Graph Embedding Problems
• Parameterized Max Min Feedback Vertex Set
• Exact Algorithms for 0-1 Integer Programs with Linear Equality Constraints
• On the Subexponential Time Complexity of CSP
• Treewidth-Aware Complexity in ASP: Not all Positive Cycles are Equally Hard
• Exploiting Treewidth for Projected Model Counting and its Limits
• Enumerating Minimal Connected Dominating Sets
• Inapproximability of VC Dimension and Littlestone's Dimension
• Parameterized complexity dichotomy for (r,ℓ)-Vertex Deletion
• On the dynamic width of the 3-colorability problem
• On the (adjacency) metric dimension of corona and strong product graphs and their local variants: combinatorial and computational results
• Self-reducible with easy decision version counting problems admit additive error approximation. Connections to counting complexity, exponential time complexity, and circuit lower bounds
• Fixing improper colorings of graphs
• What is known about Vertex Cover Kernelization?
• Parameterized Algorithms for Steiner Forest in Bounded Width Graphs
• Sampling-based bottleneck pathfinding with applications to Frechet matching
• Parameterized Complexity of Critical Node Cuts
• Sitting closer to friends than enemies, revisited
• A Polynomial Kernel for Trivially Perfect Editing
• Simpler Partial Derandomization of PPSZ for k-SAT
• On Treewidth and Stable Marriage
• On Sparsification for Computing Treewidth
• Improved approximation algorithm for the Dense-3-Subhypergraph Problem
• On the optimality of approximation schemes for the classical scheduling problem
• The role of planarity in connectivity problems parameterized by treewidth
• Consistent Subset Sampling
• 3SUM, 3XOR, Triangles
• Tight Bounds for Subgraph Isomorphism and Graph Homomorphism
• Subexponential fixed-parameter tractability of cluster editing
• Another Hamiltonian Cycle in Bipartite Pfaffian Graphs
• On Exact Algorithms for Permutation CSP
• On the Equivalence among Problems of Bounded Width
• Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis
• Approximate Clustering with Same-Cluster Queries
• A Casual Tour Around a Circuit Complexity Bound
• Universal Factor Graphs
• Tight Lower Bounds on Graph Embedding Problems
• Polynomial kernelization for removing induced claws and diamonds
• Using a Skewed Hamming Distance to Speed Up Deterministic Local Search
• Complexity of Token Swapping and Its Variants
• Tractable hypergraph properties for constraint satisfaction and conjunctive queries
• Subexponential parameterized algorithms for graphs of polynomial growth
• Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH
• Computing the Tutte polynomial in vertex-exponential time
• Tractability of Konig Edge Deletion Problems
• Ruling out FPT algorithms for Weighted Coloring on forests
• Determinant Sums for Undirected Hamiltonicity
• A Tight Analysis of Greedy Yields Subexponential Time Approximation for Uniform Decision Tree
• A Duality Between Depth-Three Formulas and Approximation by Depth-Two
• The inverse Voronoi problem in graphs
• Improved integrality gap upper bounds for TSP with distances one and two
• A Fixed-Parameter Algorithm for #SAT with Parameter Incidence Treewidth
• The Long, the Short and the Random
• Towards a more efficient approach for the satisfiability of two-variable logic
• Polynomial kernels collapse the W-hierarchy
• Complexity of counting subgraphs: only the boundedness of the vertex-cover number counts
• Parameterizing the Permanent: Genus, Apices, Minors, Evaluation mod 2^k
• Stable Marriage with Covering Constraints: A Complete Computational\n Trichotomy
• Width-parameterized SAT: Time-Space Tradeoffs
• On independence domination
• Johnson Coverage Hypothesis: Inapproximability of k-means and k-median\n in L_p metrics
• Fine-grained Meta-Theorems for Vertex Integrity
• A Note on the Complexity of Computing the Number of Reachable Vertices\n in a Digraph
• Approximating the diameter of a graph
• Algorithms and Complexity Results for Exact Bayesian Structure Learning
• Treewidth and Counting Projected Answer Sets
• Fast Hamiltonicity checking via bases of perfect matchings
• On the Parameterized Complexity of Graph Modification to First-Order Logic Properties
• FO Model Checking on Posets of Bounded Width
• Algorithms and Almost Tight Results for 3-Colorability of Small Diameter Graphs
• Computing the Tutte Polynomial in Vertex-Exponential Time
• Fully Polynomial-Time Parameterized Computations for Graphs and Matrices of Low Treewidth
• Sublinear Maximum Inner Product Search using Concomitants of Extreme Order Statistics
• Coping with the NP-Hardness of the Graph Bandwidth Problem
• Exact Algorithms for Treewidth and Minimum Fill-In
• Complexity of Grundy Coloring and Its Variants
• Tight Hardness Results for LCS and Other Sequence Similarity Measures
• Hardness of Approximation Between P and NP
• Lossy kernelization
• Parameterized Approximation Algorithms for Bidirected Steiner Network Problems
• Fixed-parameter algorithms for DAG Partitioning
• On the Parameterized Complexity of Approximating Dominating Set
• Fixed-Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs
• Diameter Spanners, Eccentricity Spanners, and Approximating Extremal Distances
• Pathwidth of cubic graphs and exact algorithms
• Strong computational lower bounds via parameterized complexity
• Invitation to Fixed-Parameter Algorithms
• Multivariate Analysis of Orthogonal Range Searching and Graph Distances Parameterized by Treewidth
• A Subexponential Parameterized Algorithm for Proper Interval Completion
• On Problems as Hard as CNF-SAT
• A measure & conquer approach for the analysis of exact algorithms
• Improved Parameterized Upper Bounds for Vertex Cover
• Subexponential Parameterized Algorithm for Minimum Fill-In
• Approximating the maximum clique minor and some subgraph homeomorphism problems
• On Directed Feedback Vertex Set Parameterized by Treewidth
• Sparsification and subexponential approximation
• Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament
• Finding Points in General Position
• Subexponential Algorithms for Unique Games and Related Problems
• On Problems Equivalent to (min,+)-Convolution
• Independent Set on P_k-Free Graphs in Quasi-Polynomial Time
• Parameterized Algorithms for Power-Efficiently Connecting Wireless Sensor Networks: Theory and Experiments
• Exponential Time Complexity of the Permanent and the Tutte Polynomial
• Time Complexity of Constraint Satisfaction via Universal Algebra
• Hitting and Harvesting Pumpkins
• Structural Decompositions of Epistemic Logic Programs
• Modern Lower Bound Techniques in Database Theory and Constraint Satisfaction
• A note on hardness of diameter approximation
• The Complexity of Satisfiability of Small Depth Circuits
• On Moderately Exponential Time for SAT
• The Exponential Time Hypothesis and the Parameterized Clique Problem
• Hardness of Equations over Finite Solvable Groups Under the Exponential Time Hypothesis
• Known Algorithms on Graphs of Bounded Treewidth are Probably Optimal
• Known Algorithms for Edge Clique Cover are Probably Optimal
• Improving exhaustive search implies superpolynomial lower bounds
• Domination When the Stars Are Out
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• Exact algorithms for the Hamiltonian cycle problem in planar graphs
• Linear Kernels and Linear-Time Algorithms for Finding Large Cuts
• Clique problem [wikipedia]
• Exponential time hypothesis [wikipedia]
• New enumeration algorithm for protein structure comparison and classification. [europepmc]
• A graph modification approach for finding core-periphery structures in protein interaction networks. [europepmc]
• Sitting Closer to Friends than Enemies, Revisited. [europepmc]
• Separating OR, SUM, and XOR Circuits. [europepmc]
• New Tools and Connections for Exponential-Time Approximation. [europepmc]
• Stable Matchings with Covering Constraints: A Complete Computational Trichotomy. [europepmc]
• Approximating Vector Scheduling: Almost Matching Upper and Lower Bounds. [europepmc]
• Obtaining a Proportional Allocation by Deleting Items. [europepmc]
• Missing value replacement in strings and applications. [europepmc]
• Tight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths. [europepmc]
• On the Fine Grained Complexity of Finite Automata Non-emptiness of Intersection [europepmc]
• A Faster Algorithm for Propositional Model Counting Parameterized by Incidence Treewidth [europepmc]