Tight (Double) Exponential Bounds for NP-Complete Problems: Treewidth and Vertex Cover Parameterizations.
Florent FoucaudEsther GalbyLiana KhazaliyaShaohua LiFionn Mc InerneyRoohani SharmaPrafullkumar TalePublished in: CoRR (2023)
Keyphrases
- vertex cover
- double exponential
- worst case
- np complete problems
- approximation algorithms
- upper bound
- lower bound
- np complete
- np hard
- graph coloring
- space complexity
- phase transition
- branch and bound algorithm
- precedence constraints
- data complexity
- max sat
- hard problems
- branch and bound
- greedy algorithm
- error bounds
- combinatorial problems
- planar graphs
- optimal solution
- search space
- polynomial time approximation
- sat problem
- constraint satisfaction
- linear programming
- constraint satisfaction problems
- heuristic search
- satisfiability problem
- computational complexity
- undirected graph
- special case
- scheduling problem
- integer programming
- conjunctive queries
- integrity constraints