From the \(W\)-hierarchy to XNLP. Classes of fixed parameter intractability. (English) Zbl 07556557
Mutzel, Petra (ed.) et al., WALCOM: algorithms and computation. 16th international conference and workshops, WALCOM 2022, Jember, Indonesia, March 24–26, 2022. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13174, 15-25 (2022).
Summary: In this short survey, a number of old and new notions from parameterized complexity are discussed. We start with looking at the \(W\)-hierarchy, including the classes \(W[1]\), \(W[2]\), \(W[P]\). Then, a recent development where problems are shown to be complete for simultaneously non-deterministic time of the form \(f(k)n^c\) and space of the form \(f(k)\log n\), is discussed. Some consequences and other notions are briefly explored.
For the entire collection see [Zbl 1490.68024].
For the entire collection see [Zbl 1490.68024].
MSC:
| 68Wxx | Algorithms in computer science |
References:
| [1] | Abrahamson, KA; Downey, RG; Fellows, MR, Fixed-parameter tractability and completeness IV: On completeness for \(W[P]\) and PSPACE analogues, Ann. Pure Appl. Logic, 73, 235-276 (1995) · Zbl 0828.68077 · doi:10.1016/0168-0072(94)00034-Z |
| [2] | Abrahamson, K.R., Ellis, J.A., Fellows, M.R., Mata, M.E.: On the complexity of fixed-parameter problems. In: Proceedings of the 30th Annual Symposium on Foundations of Computer Science, FOCS 1989, pp. 210-215 (1989) |
| [3] | Adachi, A.; Iwata, S.; Kasai, T., Classes of pebble games and complete problems, SIAM J. Comput., 8, 4, 576-586 (1979) · Zbl 0426.68021 |
| [4] | Adachi, A.; Iwata, S.; Kasai, T., Some combinatorial game problems require \({\Omega (n^k)}\) time, J. ACM, 31, 2, 361-376 (1984) · Zbl 0631.68036 · doi:10.1145/62.322433 |
| [5] | Bodlaender, HL; Kowalik, Ł.; Pilipczuk, M.; Rzążewski, P., Parameterized complexity of Bandwidth of caterpillars and Weighted Path Emulation, Graph-Theoretic Concepts in Computer Science, 15-27 (2021), Cham: Springer, Cham · Zbl 07538564 · doi:10.1007/978-3-030-86838-3_2 |
| [6] | Bodlaender, HL; Downey, RG; Fellows, MR; Hermelin, D., On problems without polynomial kernels, J. Comput. Syst. Sci., 75, 423-434 (2009) · Zbl 1192.68288 · doi:10.1016/j.jcss.2009.04.001 |
| [7] | Bodlaender, H.L., Fellows, M.R., Hallett, M.: Beyond NP-completeness for problems of bounded width: Hardness for the \(W\) hierarchy. In: Proceedings of the 26th Annual Symposium on Theory of Computing, STOC 1994, pp. 449-458. ACM Press, New York (1994) · Zbl 1345.68152 |
| [8] | Bodlaender, H.L., Groenland, C., Nederlof, J., Swennenhuis, C.M.F.: Parameterized problems complete for nondeterministic FPT time and logarithmic space. arXiv abs/2105.14882 (2021). https://arxiv.org/abs/2105.14882. To appear in proceedings FOCS 2021 |
| [9] | Bodlaender, H.L., Groenland, C., Swennenhuis, C.M.F.: Parameterized complexities of dominating and independent set reconfiguration. In: Golovach, P.A., Zehavi, M. (eds.) 16th International Symposium on Parameterized and Exact Computation, IPEC 2021. LIPIcs, vol. 214, pp. 9:1-9:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021). doi:10.4230/LIPIcs.IPEC.2021.9 · Zbl 07803587 |
| [10] | Chen, J.; Huang, X.; Kanj, IA; Xia, G., Strong computational lower bounds via parameterized complexity, J. Comput. Syst. Sci., 72, 1346-1367 (2006) · Zbl 1119.68092 · doi:10.1016/j.jcss.2006.04.007 |
| [11] | Chen, Y., Flum, J., Grohe, M.: Bounded nondeterminism and alternation in parameterized complexity theory. In: 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), Aarhus, Denmark, 7-10 July 2003, pp. 13-29. IEEE Computer Society (2003). doi:10.1109/CCC.2003.1214407 |
| [12] | Cook, S.A.: The complexity of theorem-proving procedures. In: Proceedings of the 3rd Annual Symposium on Theory of Computing, STOC 1971, pp. 151-158. ACM, New York (1971) · Zbl 0253.68020 |
| [13] | Cygan, M., Parameterized Algorithms (2015), Cham: Springer, Cham · Zbl 1334.90001 · doi:10.1007/978-3-319-21275-3 |
| [14] | Downey, RG; Fellows, MR; Ambos-Spies, K.; Homer, S.; Schöning, U., Fixed-parameter tractability and completeness III: Some structural aspects of the \(W\) hierarchy, Complexity Theory, 191-226 (1993), Cambridge: Cambridge University Press, Cambridge · Zbl 0799.68087 |
| [15] | Downey, RG; Fellows, MR, Fixed-parameter tractability and completeness I: Basic results, SIAM J. Comput., 24, 873-921 (1995) · Zbl 0830.68063 · doi:10.1137/S0097539792228228 |
| [16] | Downey, RG; Fellows, MR, Fixed-parameter tractability and completeness II: On completeness for \(W[1]\), Theoret. Comput. Sci., 141, 109-131 (1995) · Zbl 0873.68059 · doi:10.1016/0304-3975(94)00097-3 |
| [17] | Downey, RG; Fellows, MR, Parameterized Complexity (1999), New York: Springer, New York · Zbl 0961.68533 · doi:10.1007/978-1-4612-0515-9 |
| [18] | Downey, RG; Fellows, MR, Fundamentals of Parameterized Complexity (2013), London: Springer, London · Zbl 1358.68006 · doi:10.1007/978-1-4471-5559-1 |
| [19] | Dregi, MS; Lokshtanov, D.; Esparza, J.; Fraigniaud, P.; Husfeldt, T.; Koutsoupias, E., Parameterized complexity of bandwidth on trees, Automata, Languages, and Programming, 405-416 (2014), Heidelberg: Springer, Heidelberg · Zbl 1412.68080 · doi:10.1007/978-3-662-43948-7_34 |
| [20] | Elberfeld, M.; Stockhusen, C.; Tantau, T., On the space and circuit complexity of parameterized problems: classes and completeness, Algorithmica, 71, 3, 661-701 (2014) · Zbl 1312.68099 · doi:10.1007/s00453-014-9944-y |
| [21] | Fellows, MR; Langston, MA, Nonconstructive advances in polynomial-time complexity, Inf. Process. Lett., 26, 157-162 (1987) · Zbl 0637.68053 · doi:10.1016/0020-0190(87)90054-8 |
| [22] | Fellows, MR; Langston, MA, Nonconstructive tools for proving polynomial-time decidability, J. ACM, 35, 727-739 (1988) · Zbl 0652.68049 · doi:10.1145/44483.44491 |
| [23] | Fellows, MR; Rosamond, FA; Fomin, FV; Kratsch, S.; van Leeuwen, EJ, Collaborating with Hans: Some remaining wonderments, Treewidth, Kernels, and Algorithms, 7-17 (2020), Cham: Springer, Cham · Zbl 07604201 · doi:10.1007/978-3-030-42071-0_2 |
| [24] | Flum, J.; Grohe, M., The parameterized complexity of counting problems, SIAM J. Comput., 33, 4, 892-922 (2004) · Zbl 1105.68042 · doi:10.1137/S0097539703427203 |
| [25] | Flum, J.; Grohe, M., Parameterized Complexity Theory (2006), Heidelberg: Springer, Heidelberg · Zbl 1143.68016 · doi:10.1007/3-540-29953-X |
| [26] | Fomin, F.; Loksthanov, D.; Saurabh, S.; Zehavi, M., Kernelization - Theory of Parameterized Preprocessing (2019), Cambridge: Cambridge University Press, Cambridge · Zbl 1426.68003 |
| [27] | Garey, MR; Johnson, DS, Computers and Intractability, A Guide to the Theory of NP-Completeness (1979), New York: W.H. Freeman and Company, New York · Zbl 0411.68039 |
| [28] | Gurari, EM; Sudborough, IH, Improved dynamic programming algorithms for bandwidth minimization and the mincut linear arrangement problem, J. Algorithms, 5, 531-546 (1984) · Zbl 0556.68012 · doi:10.1016/0196-6774(84)90006-3 |
| [29] | Kawarabayashi, K.; Kobayashi, Y.; Reed, BA, The disjoint paths problem in quadratic time, J. Comb. Theory Ser. B, 102, 2, 424-435 (2012) · Zbl 1298.05296 · doi:10.1016/j.jctb.2011.07.004 |
| [30] | Mouawad, AE; Nishimura, N.; Raman, V.; Simjour, N.; Suzuki, A., On the parameterized complexity of reconfiguration problems, Algorithmica, 78, 1, 274-297 (2016) · Zbl 1360.68516 · doi:10.1007/s00453-016-0159-2 |
| [31] | Niedermeier, R., Invitation to Fixed-Parameter Algorithms (2006), Oxford: Oxford University Press, Oxford · Zbl 1095.68038 · doi:10.1093/acprof:oso/9780198566076.001.0001 |
| [32] | Pilipczuk, M.; Wrochna, M., On space efficiency of algorithms working on structural decompositions of graphs, ACM Trans. Comput. Theory, 9, 4, 18:1-18:36 (2018) · Zbl 1427.68130 · doi:10.1145/3154856 |
| [33] | Reingold, O., Undirected connectivity in log-space, J. ACM, 55, 4, 1-24 (2008) · Zbl 1315.68156 · doi:10.1145/1391289.1391291 |
| [34] | Saxe, JB, Dynamic programming algorithms for recognizing small-bandwidth graphs in polynomial time, SIAM J. Algebraic Discrete Methods, 1, 363-369 (1980) · Zbl 0496.68032 · doi:10.1137/0601042 |
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.
