Treewidth Is NP-Complete on Cubic Graphs.
Hans L. BodlaenderÉdouard BonnetLars JaffkeDusan KnopPaloma T. LimaMartin MilanicSebastian OrdyniakSukanya PandeyOndrej SuchýPublished in: IPEC (2023)
Keyphrases
- bounded treewidth
- np complete
- randomly generated
- np hard
- conjunctive queries
- polynomial time complexity
- computational complexity
- satisfiability problem
- constraint satisfaction problems
- data complexity
- decision problems
- search algorithm
- tractable classes
- b spline
- upper bound
- space complexity
- pspace complete
- lower bound