Back to Search
Start Over
Lower bounds for dynamic programming on planar graphs of bounded cutwidth
Lower bounds for dynamic programming on planar graphs of bounded cutwidth
- Source :
- arXiv, 2018:1806.10513v1. Cornell University Library, Journal of Graph Algorithms and Applications, 24(3), 461-482. Brown University, 13th International Symposium on Parameterized and Exact Computation (IPEC 2018)
- Publication Year :
- 2018
-
Abstract
- Many combinatorial problems can be solved in time O∗(ctw) on graphs of treewidth tw, for a problem-specific constant c. In several cases, matching upper and lower bounds on c are known based on the Strong Exponential Time Hypothesis (SETH). In this paper we investigate the complexity of solving problems on graphs of bounded cutwidth, a graph parameter that takes larger values than treewidth. We strengthen earlier treewidth-based lower bounds to show that, assuming SETH, Independent Set cannot be solved in O∗((2 − ε)ctw) time, and Dominating Set cannot be solved in O∗((3 − ε)ctw) time. By designing a new crossover gadget, we extend these lower bounds even to planar graphs of bounded cutwidth or treewidth. Hence planarity does not help when solving Independent Set or Dominating Set on graphs of bounded width. This sharply contrasts the fact that in many settings, planarity allows problems to be solved much more efficiently.
- Subjects :
- FOS: Computer and information sciences
Computational Complexity
General Computer Science
Matching (graph theory)
Data Structures and Algorithms
G.2.2
Computational Complexity (cs.CC)
Strong exponential time hypothesis
Upper and lower bounds
Theoretical Computer Science
symbols.namesake
Dominating set
68R10, 05C10, 05C69, 05C85
TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY
Computer Science - Data Structures and Algorithms
Data Structures and Algorithms (cs.DS)
Computer Science::Data Structures and Algorithms
Mathematics
Discrete mathematics
F.2.2
000 Computer science, knowledge, general works
Exponential time hypothesis
Cutwidth
Lower bounds
Computer Science Applications
Planar graph
Treewidth
Computer Science - Computational Complexity
Computational Theory and Mathematics
Independent set
Bounded function
Computer Science
Planarization
symbols
Geometry and Topology
MathematicsofComputing_DISCRETEMATHEMATICS
Subjects
Details
- Language :
- English
- ISSN :
- 15261719
- Database :
- OpenAIRE
- Journal :
- arXiv, 2018:1806.10513v1. Cornell University Library, Journal of Graph Algorithms and Applications, 24(3), 461-482. Brown University, 13th International Symposium on Parameterized and Exact Computation (IPEC 2018)
- Accession number :
- edsair.doi.dedup.....15c5c81cf9815e0ee1c19506a4c2daeb