{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T10:40:35Z","timestamp":1760179235431,"version":"build-2065373602"},"reference-count":38,"publisher":"MDPI AG","issue":"8","license":[{"start":{"date-parts":[[2020,8,14]],"date-time":"2020-08-14T00:00:00Z","timestamp":1597363200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>This paper provides an overview of the field of parameterized parallel complexity by surveying previous work in addition to presenting a few new observations and exploring potential new directions. In particular, we present a general view of how known FPT techniques, such as bounded search trees, color coding, kernelization, and iterative compression, can be modified to produce fixed-parameter parallel algorithms.<\/jats:p>","DOI":"10.3390\/a13080197","type":"journal-article","created":{"date-parts":[[2020,8,14]],"date-time":"2020-08-14T08:28:35Z","timestamp":1597393715000},"page":"197","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["A Brief Survey of Fixed-Parameter Parallelism"],"prefix":"10.3390","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5221-8421","authenticated-orcid":false,"given":"Faisal N.","family":"Abu-Khzam","sequence":"first","affiliation":[{"name":"Department of Computer Science and Mathematics, Lebanese American University, Beirut 1102 2801, Lebanon"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Karam","family":"Al Kontar","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Mathematics, Lebanese American University, Beirut 1102 2801, Lebanon"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2020,8,14]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Cesati, M., and Di Ianni, M. (1998, January 1\u20134). Parameterized parallel complexity. Proceedings of the European Conference on Parallel Processing, Southampton, UK.","DOI":"10.1007\/BFb0057945"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Abu-Khzam, F.N., Li, S., Markarian, C., Heide, F.M.A.D., and Podlipyan, P. (2016). On the Parameterized Parallel Complexity and the Vertex Cover Problem. Lecture Notes in Computer Science, Proceedings of the Combinatorial Optimization and Applications, Hong Kong, China, 16\u201318 December 2016, Springer.","DOI":"10.1007\/978-3-319-48749-6_35"},{"key":"ref_3","first-page":"73","article-title":"Computational tractability: The view from mars","volume":"69","author":"Downey","year":"1999","journal-title":"Bull. EATCS"},{"key":"ref_4","unstructured":"Papadimitriou, C. (1993). Section 15.3: The class NC. Computational Complexity, Addison Wesley. [1st ed.]."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"1725","DOI":"10.1137\/S0097539795289859","article-title":"Parallel algorithms with optimal speedup for bounded treewidth","volume":"27","author":"Bodlaender","year":"1998","journal-title":"SIAM J. Comput."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/j.tcs.2018.11.006","article-title":"Efficient parallel algorithms for parameterized problems","volume":"786","author":"Li","year":"2019","journal-title":"Theor. Comput. Sci."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Diestel, R. (2017). Graph Theory. Grad. Texts Math., 173.","DOI":"10.1007\/978-3-662-53622-3_7"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Lepist\u00f6, T., and Salomaa, A. (1988, January 11\u201315). Dynamic programming on graphs with bounded treewidth. Proceedings of the Automata, Languages and Programming, Tampere, Finland.","DOI":"10.1007\/3-540-19488-6"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1007\/BF02020961","article-title":"Transitiv orientierbare graphen","volume":"18","author":"Gallai","year":"1967","journal-title":"Acta Math. Hung."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Gajarsk\u1ef3, J., Lampis, M., and Ordyniak, S. (2013, January 4\u20136). Parameterized algorithms for modular-width. Proceedings of the International Symposium on Parameterized and Exact Computation, Sophia Antipolis, France.","DOI":"10.1007\/978-3-319-03898-8_15"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Arora, S., and Barak, B. (2009). Computational Complexity: A Modern Approach, Cambridge University Press.","DOI":"10.1017\/CBO9780511804090"},{"key":"ref_12","unstructured":"Clote, P., and Kranakis, E. (2013). Boolean Functions and Computation Models, Springer Science & Business Media."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/s00453-006-1214-1","article-title":"Scalable Parallel Algorithms for FPT Problems","volume":"45","author":"Langston","year":"2006","journal-title":"Algorithmica"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/j.jpdc.2015.07.006","article-title":"On scalable parallel recursive backtracking","volume":"84","author":"Daudjee","year":"2015","journal-title":"J. Parallel Distrib. Comput."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/0020-0190(88)90168-8","article-title":"Parallelism and the feedback vertex set problem","volume":"28","author":"Bovet","year":"1988","journal-title":"Inf. Process. Lett."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"560","DOI":"10.1137\/0222038","article-title":"Nondeterminism within P","volume":"22","author":"Buss","year":"1993","journal-title":"SIAM J. Comput."},{"key":"ref_17","first-page":"224","article-title":"Fast Parallel Fixed-parameter Algorithms via Color Coding","volume":"Volume 43","author":"Husfeldt","year":"2015","journal-title":"Proceedings of the 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Abu-Khzam, F.N., Li, S., Markarian, C., Heide, F.M.A.D., and Podlipyan, P. (2017). Modular-Width: An Auxiliary Parameter for Parameterized Parallel Complexity. Lecture Notes in Computer Science, Proceedings of the Frontiers in Algorithmics, Chengdu, China, 23\u201325 June 2017, Springer.","DOI":"10.1007\/978-3-319-59605-1_13"},{"key":"ref_19","unstructured":"Bannach, M., and Tantau, T. (2018). Computing kernels in parallel: Lower and upper bounds. arXiv."},{"key":"ref_20","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., and Stein, C. (2009). Introduction to Algorithms, The MIT Press. [3rd ed.]."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Abu-Khzam, F.N., Langston, M.A., Mouawad, A.E., and Nolan, C.P. (2010, January 11\u201313). A hybrid graph representation for recursive backtracking algorithms. Proceedings of the International Workshop on Frontiers in Algorithmics, Wuhan, China.","DOI":"10.1007\/978-3-642-14553-7_15"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"479","DOI":"10.1007\/s00224-007-1345-z","article-title":"An O (2 O (k) n 3) FPT algorithm for the undirected feedback vertex set problem","volume":"41","author":"Dehne","year":"2007","journal-title":"Theory Comput. Syst."},{"key":"ref_23","first-page":"32","article-title":"A 4k2 kernel for feedback vertex set","volume":"6","year":"2010","journal-title":"ACM Trans. Algorithms (TALG)"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Downey, R.G., and Fellows, M.R. (1995). Parameterized computational feasibility. Feasible mathematics II, Springer.","DOI":"10.1007\/978-1-4612-2566-9_7"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., and Saurabh, S. (2015). Parameterized Algorithms, Springer.","DOI":"10.1007\/978-3-319-21275-3"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1090\/dimacs\/049\/04","article-title":"Parameterized complexity: A framework for systematically confronting computational intractability","volume":"Volume 49","author":"Downey","year":"1999","journal-title":"Contemporary Trends in Discrete Mathematics: From DIMACS and DIMATIA to the Future"},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Panolan, F., Ramanujan, M.S., and Saurabh, S. (2017, January 19\u201323). Lossy Kernelization. Proceedings of the STOC 2017 49th Annual ACM SIGACT Symposium on Theory of Computing, Montreal, QC, Canada.","DOI":"10.1145\/3055399.3055456"},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Alon, N., Yuster, R., and Zwick, U. (1994, January 23\u201325). Color-coding: A New Method for Finding Simple Paths, Cycles and Other Small Subgraphs Within Large Graphs. Proceedings of the STOC\u201994 Twenty-Sixth Annual ACM Symposium on Theory of Computing, Montreal, QC, Canada.","DOI":"10.1145\/195058.195179"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"844","DOI":"10.1145\/210332.210337","article-title":"Color-coding","volume":"42","author":"Alon","year":"1995","journal-title":"J. ACM"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1007\/s00224-004-1178-y","article-title":"Graph-Modeled Data Clustering: Exact Algorithms for Clique Generation","volume":"38","author":"Gramm","year":"2005","journal-title":"Theory Comput. Syst."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1016\/j.jda.2017.07.003","article-title":"On the complexity of multi-parameterized cluster editing","volume":"45","year":"2017","journal-title":"J. Discret. Algorithms"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"2259","DOI":"10.1016\/j.dam.2012.05.019","article-title":"Cluster editing with locally bounded modifications","volume":"160","author":"Komusiewicz","year":"2012","journal-title":"Discret. Appl. Math."},{"key":"ref_33","first-page":"171","article-title":"Generalized Graph Clustering: Recognizing (p, q)-Cluster Graphs","volume":"Volume 6410","author":"Thilikos","year":"2010","journal-title":"Lecture Notes in Computer Science, Proceedings of the Graph Theoretic Concepts in Computer Science\u201436th International Workshop, WG 2010, Zar\u00f3s, Crete, Greece, 28\u201330 June 2010"},{"key":"ref_34","first-page":"257","article-title":"Linear Kernels in Linear Time, or How to Save k Colors in O(n2) Steps","volume":"Volume 3353","author":"Hromkovic","year":"2004","journal-title":"Lecture Notes in Computer Science, Proceedingsof the Graph-Theoretic Concepts in Computer Science, 30th International Workshop, WG 2004, Bad Honnef, Germany, 21\u201323 June 2004"},{"key":"ref_35","unstructured":"Abu-Khzam, F.N., Langston, M.A., and Suters, W.H. (2005, January 3\u20136). Fast, effective vertex cover kernelization: A tale of two algorithms. Proceedings of the 2005 ACS\/IEEE International Conference on Computer Systems and Applications (AICCSA 2005), Cairo, Egypt."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1007\/s00224-007-1328-0","article-title":"Crown Structures for Vertex Cover Kernelization","volume":"41","author":"Fellows","year":"2007","journal-title":"Theory Comput. Syst."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"292","DOI":"10.1016\/j.dam.2007.03.026","article-title":"Crown reductions for the Minimum Weighted Vertex Cover problem","volume":"156","year":"2008","journal-title":"Discret. Appl. Math."},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Williamson, D.P., and Shmoys, D.B. (2011). The Design of Approximation Algorithms, Cambridge University Press.","DOI":"10.1017\/CBO9780511921735"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/8\/197\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T10:00:42Z","timestamp":1760176842000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/8\/197"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,14]]},"references-count":38,"journal-issue":{"issue":"8","published-online":{"date-parts":[[2020,8]]}},"alternative-id":["a13080197"],"URL":"https:\/\/doi.org\/10.3390\/a13080197","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2020,8,14]]}}}