On Problems as Hard as CNF-SAT

DOI10.1145/2925416zbMath1442.68064arXiv1112.2275OpenAlexW2404960361MaRDI QIDQ4962605

Yoshio Okamoto, Jesper Nederlof, Daniel Lokshtanov, Marek Cygan, Dániel Marx, Ramamohan Paturi, Holger Dell, Magnus Wahlström, Saket Saurabh

Publication date: 5 November 2018

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1112.2275

zbMATH Keywords

reduction satisfiability strong exponential-time hypothesis optimal growth rate

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computational aspects of satisfiability (68R07)

Related Items (50)

Scheduling lower bounds via AND subset sum ⋮ Structural parameterizations of clique coloring ⋮ The Parity of Set Systems Under Random Restrictions with Applications to Exponential Time Problems ⋮ Maximum Minimal Vertex Cover Parameterized by Vertex Cover ⋮ On the Equivalence among Problems of Bounded Width ⋮ Block interpolation: a framework for tight exponential-time counting complexity ⋮ On Treewidth and Stable Marriage: Parameterized Algorithms and Hardness Results (Complete Characterization) ⋮ Known Algorithms for Edge Clique Cover are Probably Optimal ⋮ Structural parameterizations with modulator oblivion ⋮ Extending the kernel for planar Steiner tree to the number of Steiner vertices ⋮ Parameterized and Subexponential-Time Complexity of Satisfiability Problems and Applications ⋮ Maximum Minimal Vertex Cover Parameterized by Vertex Cover ⋮ On exact algorithms for the permutation CSP ⋮ A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics ⋮ An ETH-tight algorithm for bidirected Steiner connectivity ⋮ Unnamed Item ⋮ Constrained hitting set problem with intervals: hardness, FPT and approximation algorithms ⋮ Constrained hitting set problem with intervals ⋮ Unnamed Item ⋮ Finer Tight Bounds for Coloring on Clique-Width ⋮ Parameterized Dynamic Variants of Red-Blue Dominating Set ⋮ Solving the 2-disjoint connected subgraphs problem faster than $2^n$ ⋮ Path Contraction Faster than $2^n$ ⋮ Edge bipartization faster than $2^k$ ⋮ Parameterized algorithms for list $K$-cycle ⋮ On the Optimality of Pseudo-polynomial Algorithms for Integer Programming ⋮ Inclusion/exclusion meets measure and conquer ⋮ Temporal vertex cover with a sliding time window ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Dynamic parameterized problems ⋮ Width, depth, and space: tradeoffs between branching and dynamic programming ⋮ Parameterized complexity of conflict-free set cover ⋮ Lower bounds for the happy coloring problems ⋮ Fine-grained complexity of safety verification ⋮ Many-visits TSP revisited ⋮ Fine-Grained Reductions and Quantum Speedups for Dynamic Programming. ⋮ Complexity of the Steiner Network Problem with Respect to the Number of Terminals ⋮ Path Contraction Faster Than 2^n ⋮ Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression ⋮ Revisiting connected vertex cover: FPT algorithms and lossy kernels ⋮ Refined parameterizations for computing colored cuts in edge-colored graphs ⋮ On the Complexity of Bounded Context Switching. ⋮ Parameterized Pre-Coloring Extension and List Coloring Problems ⋮ Moderate exponential-time algorithms for scheduling problems ⋮ Exponential-time quantum algorithms for graph coloring problems ⋮ A completeness theory for polynomial (Turing) kernelization ⋮ Unnamed Item ⋮ Hardness of approximation for knapsack problems ⋮ Constrained multilinear detection and generalized graph motifs

This page was built for publication: On Problems as Hard as CNF-SAT