Lower bounds for dynamic programming on planar graphs of bounded cutwidth. (English) Zbl 1446.05087
Summary: Many combinatorial problems can be solved in time \(\mathcal{O}^*(c^{\text{tw}})\) on graphs of treewidth \(\text{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-\varepsilon)^{\text{ctw}})\) time, and Dominating Set cannot be solved in \(O^*((3-\varepsilon)^{\text{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.
MSC:
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 90C39 | Dynamic programming |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 90C60 | Abstract computational complexity for mathematical programming problems |
References:
| [1] | J. Baste and I. Sau. The role of planarity in connectivity problems parameterized by treewidth.Theor. Comput. Sci., 570:1-14, 2015. · Zbl 1306.05123 |
| [2] | A. Bj¨orklund, T. Husfeldt, P. Kaski, and M. Koivisto.Fourier meets M¨obius: Fast subset convolution. InProc. 39th STOC, pages 67-74. ACM, 2007. · Zbl 1232.68188 · doi:10.1145/1250790.1250801 |
| [3] | H. L. Bodlaender. A partialk-arboretum of graphs with bounded treewidth. Theor. Comput. Sci., 209(1-2):1-45, 1998. · Zbl 0912.68148 · doi:10.1016/S0304-3975(97) |
| [4] | H. L. Bodlaender, M. Cygan, S. Kratsch, and J. Nederlof. Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth.Inf. Comput., 243:86-111, 2015. · Zbl 1327.68126 · doi:10.1016/j.ic.2014. |
| [5] | H. L. Bodlaender and A. M. C. A. Koster. Combinatorial optimization on graphs of bounded treewidth.Comput. J., 51(3):255-269, 2008. |
| [6] | J. Chen, I. A. Kanj, and W. Jia. Vertex cover: Further observations and further improvements.J. Algorithms, 41(2):280-301, 2001. · Zbl 1017.68087 · doi:10.1006/ |
| [7] | B. Courcelle. The monadic second-order logic of graphs I: Recognizable sets of finite graphs.Inf. Comput., 85(1):12-75, 1990. · Zbl 0722.03008 · doi:10.1016/ |
| [8] | M. Cygan, S. Kratsch, and J. Nederlof. Fast Hamiltonicity checking via bases of perfect matchings.J. ACM, 65(3):12:1-12:46, 2018. · Zbl 1426.68117 · doi:10.1145/ |
| [9] | M. Cygan, J. Nederlof, M. Pilipczuk, M. Pilipczuk, J. M. M. van Rooij, and J. O. Wojtaszczyk. Solving connectivity problems parameterized by treewidth in single exponential time. InProc. 52nd FOCS, pages 150-159, 2011. · Zbl 1292.68122 · doi:10.1109/FOCS.2011.23 |
| [10] | E. D. Demaine and M. Hajiaghayi. The bidimensionality theory and its algorithmic applications.Comput. J., 51(3):292-302, 2008. · doi:10.1093/ |
| [11] | J. D´ıaz, J. Petit, and M. J. Serna. A survey of graph layout problems. ACM Comput. Surv., 34(3):313-356, 2002. · doi:10.1145/568522.568523 |
| [12] | D. Eppstein. Pathwidth of planarized drawing ofK3,n. TheoryCS StackExchange question, 2016. URL: |
| [13] | D. Eppstein. The effect of planarization on width.J. Graph Algorithms Appl., 22(3):461-481, 2018. · Zbl 1398.05141 · doi:10.7155/jgaa.00468 |
| [14] | F. V. Fomin, D. Lokshtanov, F. Panolan, and S. Saurabh. Efficient computation of representative families with applications in parameterized and exact algorithms.J. ACM, 63(4):29:1-29:60, 2016. · Zbl 1410.05212 · doi:10.1145/2886094 |
| [15] | M. Garey, D. Johnson, and L. Stockmeyer. Some simplified NP-complete graph problems.Theor. Comput. Sci., 1(3):237-267, 1976. · Zbl 0338.05120 · doi:10.1016/ |
| [16] | A. C. Giannopoulou, M. Pilipczuk, J. Raymond, D. M. Thilikos, and M. Wrochna. Cutwidth: Obstructions and algorithmic aspects.Algorithmica, 81(2):557-588, 2019. · Zbl 1414.68035 · doi:10.1007/s00453-018-0424-7 |
| [17] | R. Impagliazzo and R. Paturi. On the complexity ofk-SAT.J. Comput. Syst. Sci., 62(2):367-375, 2001. · Zbl 0990.68079 · doi:10.1006/jcss.2000.1727 |
| [18] | R. Impagliazzo, R. Paturi, and F. Zane. Which problems have strongly exponential complexity?J. Comput. Syst. Sci., 63(4):512-530, 2001. · Zbl 1006.68052 |
| [19] | B. M. P. Jansen and J. Nederlof. Computing the chromatic number using graph decompositions via matrix rank. InProc. 26th ESA, pages 47:1- 47:15, 2018. · Zbl 1431.68053 |
| [20] | B. M. P. Jansen and J. Nederlof. Computing the chromatic number using graph decompositions via matrix rank.Theor. Comput. Sci., 795:520-539, 2019. · Zbl 1431.68053 · doi:10.1016/j.tcs.2019.08.006 |
| [21] | B. M. P. Jansen and J. J. H. M. Wulms. Lower bounds for protrusion replacement by counting equivalence classes.Discret. Appl. Math., 278:12- 27, 2020. · Zbl 1437.05224 · doi:10.1016/j.dam.2019.02.024 |
| [22] | E. Korach and N. Solel. Tree-width, path-width, and cutwidth.Discrete Appl. Math., 43(1):97-101, 1993. · Zbl 0788.05057 · doi:10.1016/0166-218X(93)90171-J |
| [23] | D. Lokshtanov, D. Marx, and S. Saurabh. Known algorithms on graphs of bounded treewidth are probably optimal. InProc. 22nd SODA, pages 777-789, 2011. · Zbl 1373.68242 · doi:10.1137/1.9781611973082.61 |
| [24] | D. Lokshtanov, D. Marx, and S. Saurabh. Lower bounds based on the exponential time hypothesis.Bull. EATCS, 105:41-72, 2011. URL: · Zbl 1258.68068 |
| [25] | D. Lokshtanov, D. Marx, and S. Saurabh. Known algorithms on graphs of bounded treewidth are probably optimal.ACM Trans. Algorithms, 14(2):13:1-13:30, 2018. · Zbl 1454.68110 · doi:10.1145/3170442 |
| [26] | D. Marx. The square root phenomenon in planar graphs. InProc. 3rd FAW-AAIM, page 1, 2013. · doi:10.1007/978-3-642-38756-2_1 |
| [27] | M. Pilipczuk. Problems parameterized by treewidth tractable in single exponential time: A logical approach. InProc. 36th MFCS, pages 520-531, 2011. · Zbl 1343.68120 · doi:10.1007/978-3-642-22993-0_47 |
| [28] | D. M. Thilikos, M. J. Serna, and H. L. Bodlaender. Cutwidth I: A linear time fixed parameter algorithm.J. Algorithms, 56(1):1-24, 2005. · Zbl 1161.68856 |
| [29] | D. M. Thilikos, M. J. Serna, and H. L. Bodlaender. Cutwidth II: Algorithms for partial w-trees of bounded degree.J. Algorithms, 56(1):25-49, 2005. · Zbl 1161.68857 · doi:10.1016/j.jalgor.2004.12.003 |
| [30] | J. M. M. van Rooij, H. L. Bodlaender, and P. Rossmanith.Dynamic programming on tree decompositions using generalised fast subset convolution.InProc. 17th ESA, pages 566-577, 2009. · Zbl 1256.68157 · doi:10.1007/ |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
