{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,25]],"date-time":"2026-07-25T21:50:34Z","timestamp":1785016234979,"version":"3.55.0"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2024,3,25]],"date-time":"2024-03-25T00:00:00Z","timestamp":1711324800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Commun. ACM"],"published-print":{"date-parts":[[2024,4]]},"abstract":"<jats:p>The challenge of transforming polynomial-time algorithms to really efficient ones.<\/jats:p>","DOI":"10.1145\/3624713","type":"journal-article","created":{"date-parts":[[2024,3,25]],"date-time":"2024-03-25T10:55:52Z","timestamp":1711364152000},"page":"70-79","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Fast Parameterized Preprocessing for Polynomial-Time Solvable Graph Problems"],"prefix":"10.1145","volume":"67","author":[{"given":"Anne-Sophie","family":"Himmel","sequence":"first","affiliation":[{"name":"TU Berlin, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"George B.","family":"Mertzios","sequence":"additional","affiliation":[{"name":"Durham University, U.K"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andr\u00e9","family":"Nichterlein","sequence":"additional","affiliation":[{"name":"TU Berlin, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rolf","family":"Niedermeier","sequence":"additional","affiliation":[{"name":"TU Berlin, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,3,25]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"753","article-title":"On dynamic approximate shortest paths for planar graphs with worst-case costs","volume":"740","author":"Abraham I.","year":"2016","unstructured":"Abraham, I. et al. On dynamic approximate shortest paths for planar graphs with worst-case costs. In Proceedings of SODA. SIAM, 2016, 740--753.","journal-title":"Proceedings of SODA. SIAM"},{"key":"e_1_2_1_2_1","first-page":"281","article-title":"A depth-first algorithm to reduce graphs in linear time","volume":"273","author":"Bartha M.","year":"2009","unstructured":"Bartha, M. and Kresz, M. A depth-first algorithm to reduce graphs in linear time. In Proceedings of SYNASC. IEEE, 2009, 273--281.","journal-title":"Proceedings of SYNASC. IEEE"},{"key":"e_1_2_1_3_1","volume-title":"et al. Route planning in transportation networks. Algorithm Engineering---Selected Results and Surveys 9220. LNCS","author":"Bast H.","year":"2016","unstructured":"Bast, H. et al. Route planning in transportation networks. Algorithm Engineering---Selected Results and Surveys 9220. LNCS, Springer, 2016, 19--80; (2016)."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(83)90078-9"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.50.1.3.17780"},{"key":"e_1_2_1_6_1","volume-title":"Maximum matching in general graphs without explicit consideration of blossoms revisited. Technical report","author":"Blum N.","year":"2015","unstructured":"Blum, N. Maximum matching in general graphs without explicit consideration of blossoms revisited. Technical report, 2015; http:\/\/arxiv.org\/abs\/1509.04927."},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of WG 344","author":"Bodlaender H.L.","year":"1988","unstructured":"Bodlaender, H.L. NC-algorithms for graphs with small treewidth. In Proceedings of WG 344. LNCS, Springer 1988, 1--10."},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of SoCG 51","author":"Borradaile G.","year":"2016","unstructured":"Borradaile, G., Eppstein, D., Nayyeri, A., and Wulff-Nilsen, C. All-pairs minimum cuts in near-linear time for surface-embedded graphs. In Proceedings of SoCG 51, 22. Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 2016, 1--16."},{"key":"e_1_2_1_9_1","first-page":"670","article-title":"Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless SETH fails","volume":"661","author":"Bringmann K","year":"2014","unstructured":"Bringmann, K. Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless SETH fails. In Proceedings of FOCS. IEEE, 2014, 661--670.","journal-title":"Proceedings of FOCS. IEEE"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of STACS 126","author":"Bringmann K.","year":"2019","unstructured":"Bringmann, K. Fine-grained complexity theory (tutorial). In Proceedings of STACS 126, 4. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, 2019, 1--7."},{"key":"e_1_2_1_11_1","first-page":"1235","article-title":"Multivariate finegrained complexity of longest common subsequence","volume":"1216","author":"Bringmann K.","year":"2018","unstructured":"Bringmann, K. and K\u00fcnnemann, M. Multivariate finegrained complexity of longest common subsequence. In Proceedings of SODA. SIAM, 2018, 1216--1235.","journal-title":"Proceedings of SODA. SIAM"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004530010016"},{"key":"e_1_2_1_13_1","volume-title":"The PACE 2017 Parameterized Algorithms and Computational Experiments Challenge: The second iteration. In Proceedings of IPEC 89","author":"Dell H.","year":"2018","unstructured":"Dell, H., Komusiewicz, C., Talmon, N., and Weller, M. The PACE 2017 Parameterized Algorithms and Computational Experiments Challenge: The second iteration. In Proceedings of IPEC 89, 30. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 2018, 1--12."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.2014.0579"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2529989"},{"key":"e_1_2_1_17_1","volume-title":"Kernelization: Theory of Parameterized Preprocessing","author":"Fomin F.V.","year":"2019","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S., and Zehavi, M. Kernelization: Theory of Parameterized Preprocessing. Cambridge University Press, 2019."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2017.05.017"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.1995.2.139"},{"key":"e_1_2_1_20_1","volume-title":"Annals of Discrete Mathematics","author":"Golumbic M.C.","year":"2004","unstructured":"Golumbic, M.C. Annals of Discrete Mathematics, 2nd edition. Algorithmic Graph Theory and Perfect Graphs 57. North-Holland Publishing Co., 2004.","edition":"2"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of 2021 KDD. ACM, 467--477","author":"Gu J.","unstructured":"Gu, J., Zheng, W., Cai, Y., and Peng, P. Towards computing a near-maximum weighted independent set on massive graphs. In Proceedings of 2021 KDD. ACM, 467--477."},{"key":"e_1_2_1_22_1","first-page":"173","article-title":"A structural view on parameterizing problems: Distance from triviality","volume":"162","author":"Guo J.","year":"2004","unstructured":"Guo, J., H\u00fcffner, F., and Niedermeier, R. A structural view on parameterizing problems: Distance from triviality. In Proceedings of IWPEC. LNCS 3162. Springer, 2004, 162--173.","journal-title":"Proceedings of IWPEC. LNCS 3162. Springer"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1233481.1233493"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of ESA 173","author":"Henzinger M.","year":"2020","unstructured":"Henzinger, M., Noe, A., Schulz, C., and Strash, D. Finding all global minimum cuts in practice. In Proceedings of ESA 173, 59. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 2020, 1--20."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9411-3"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of STACS 96","author":"Iwata Y.","year":"2018","unstructured":"Iwata, Y., Ogasawara, T., and Ohsaka, N. On the power of tree-depth for fully polynomial FPT algorithms. In Proceedings of STACS 96, 41. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 2018, 1--14."},{"key":"e_1_2_1_27_1","first-page":"375","article-title":"Maximum matchings in sparse random graphs","volume":"364","author":"Karp R.M.","year":"1981","unstructured":"Karp, R.M. and Sipser, M. Maximum matchings in sparse random graphs. In Proceedings of FOCS. IEEE, 1981, 364--375.","journal-title":"Proceedings of FOCS. IEEE"},{"key":"e_1_2_1_28_1","first-page":"132","article-title":"Computing maximum-cardinality matchings in sparse general graphs","volume":"121","author":"Kececioglu J.D.","year":"1998","unstructured":"Kececioglu, J.D. and Pecqueur, A.J. Computing maximum-cardinality matchings in sparse general graphs. In Proceedings of WAE. Max-Planck-Institut f\u00fcr Informatik, 1998, 121--132.","journal-title":"Proceedings of WAE. Max-Planck-Institut f\u00fcr Informatik"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3439801"},{"key":"e_1_2_1_30_1","volume-title":"SNAP Datasets: Stanford large network dataset collection","author":"Leskovec J.","year":"2014","unstructured":"Leskovec, J. and Krevl, A. SNAP Datasets: Stanford large network dataset collection. June 2014; http:\/\/snap.stanford.edu\/data."},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the 2019 ICDT 127","author":"Maniu S.","unstructured":"Maniu, S., Senellart, P., and Jog, S. An experimental study of the treewidth of real-world graph data. In Proceedings of the 2019 ICDT 127, 12. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 1--18."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2500119"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-020-00736-0"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of STACS 5. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik","author":"Niedermeier R.","year":"2010","unstructured":"Niedermeier, R. Reflections on multivariate algorithmics and problem parameterization. In Proceedings of STACS 5. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 2010, 17--32"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3232535"},{"key":"e_1_2_1_37_1","volume-title":"Computing tree decompositions with flowcutter: Technical report","author":"Strasser B.","year":"2017","unstructured":"Strasser, B. Computing tree decompositions with flowcutter: Technical report, 2017; http:\/\/arxiv.org\/abs\/1709.08949."},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of ICM. World Scientific","author":"Vassilevska Williams V.","year":"2018","unstructured":"Vassilevska Williams, V. On some fine-grained questions in algorithms and complexity. In Proceedings of ICM. World Scientific, 2018."},{"key":"e_1_2_1_39_1","first-page":"5","article-title":"Subcubic equivalences between path, matrix, and triangle problems","volume":"65","author":"Vassilevska Williams V.","year":"2018","unstructured":"Vassilevska Williams, V. and Williams, R.R. Subcubic equivalences between path, matrix, and triangle problems. J. ACM 65, 5 (2018), 27:1--27:38.","journal-title":"J. ACM"},{"key":"e_1_2_1_40_1","first-page":"1178","article-title":"Backdoors to typical case complexity","volume":"1173","author":"Williams R.","year":"2003","unstructured":"Williams, R., Gomes, C.P., and Selman, B. Backdoors to typical case complexity. In Proceedings of IJCAI. Morgan Kaufmann, 2003, 1173--1178.","journal-title":"Proceedings of IJCAI. Morgan Kaufmann"}],"container-title":["Communications of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3624713","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3624713","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,23]],"date-time":"2025-08-23T18:30:42Z","timestamp":1755973842000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3624713"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,25]]},"references-count":40,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,4]]}},"alternative-id":["10.1145\/3624713"],"URL":"https:\/\/doi.org\/10.1145\/3624713","relation":{},"ISSN":["0001-0782","1557-7317"],"issn-type":[{"value":"0001-0782","type":"print"},{"value":"1557-7317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,25]]},"assertion":[{"value":"2024-03-25","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}