{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,28]],"date-time":"2025-11-28T21:10:23Z","timestamp":1764364223629,"version":"3.41.0"},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2016,3,1]],"date-time":"2016-03-01T00:00:00Z","timestamp":1456790400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100002322","name":"Coordena\u00e7\u00e3o de Aperfei\u00e7oamento de Pessoal de N\u00edvel Superior","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100002322","id-type":"DOI","asserted-by":"publisher"}]},{"name":"PUC-Rio - Pontif\u00edcia Universidade Cat\u00f3lica do Rio de Janeiro"},{"DOI":"10.13039\/501100000923","name":"Australian Research Council","doi-asserted-by":"publisher","award":["DP1094516, DP110101104"],"award-info":[{"award-number":["DP1094516, DP110101104"]}],"id":[{"id":"10.13039\/501100000923","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004586","name":"Funda\u00e7\u00e3o Carlos Chagas Filho de Amparo \u00e0 Pesquisa do Estado do Rio de Janeiro","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100004586","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003593","name":"Conselho Nacional de Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Math. Softw."],"published-print":{"date-parts":[[2016,3]]},"abstract":"<jats:p>\n            Optimal Morse matchings reveal essential structures of cell complexes that lead to powerful tools to study discrete geometrical objects, in particular, discrete 3-manifolds. However, such matchings are known to be NP-hard to compute on 3-manifolds through a reduction to the erasability problem. Here, we refine the study of the complexity of problems related to discrete Morse theory in terms of parameterized complexity. On the one hand, we prove that the erasability problem is\n            <jats:italic>W<\/jats:italic>\n            [\n            <jats:italic>P<\/jats:italic>\n            ]-complete on the natural parameter. On the other hand, we propose an algorithm for computing optimal Morse matchings on triangulations of 3-manifolds, which is fixed-parameter tractable in the treewidth of the bipartite graph representing the adjacency of the 1- and 2-simplices. This algorithm also shows fixed-parameter tractability for problems such as erasability and maximum alternating cycle-free matching. We further show that these results are also true when the treewidth of the dual graph of the triangulated 3-manifold is bounded. Finally, we discuss the topological significance of the chosen parameters and investigate the respective treewidths of simplicial and generalized triangulations of 3-manifolds.\n          <\/jats:p>","DOI":"10.1145\/2738034","type":"journal-article","created":{"date-parts":[[2016,3,3]],"date-time":"2016-03-03T16:20:48Z","timestamp":1457022048000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Parameterized Complexity of Discrete Morse Theory"],"prefix":"10.1145","volume":"42","author":[{"given":"Benjamin A.","family":"Burton","sequence":"first","affiliation":[{"name":"School of Mathematics and Physics, The University of Queensland, Brisbane, Australia"}]},{"given":"Thomas","family":"Lewiner","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Pontif\u00edcia Universidade Cat\u00f3lica, Rio de Janeiro, Brazil"}]},{"given":"Jo\u00e3o","family":"Paix\u00e3o","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Pontif\u00edcia Universidade Cat\u00f3lica, Rio de Janeiro, Brazil"}]},{"given":"Jonathan","family":"Spreer","sequence":"additional","affiliation":[{"name":"School of Mathematics and Physics, The University of Queensland, Brisbane, Australia"}]}],"member":"320","published-online":{"date-parts":[[2016,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(94)00034-Z"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-05-03919-X"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-30238-1_2"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1080\/10586458.2013.865281"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511662041.008"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30577-4_1"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167161"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0049"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1080\/10586458.2004.10504538"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993886.1993901"},{"key":"e_1_2_1_12_1","unstructured":"B. A. Burton R. Budney W. Pettersson and others. 1999--2014. Regina: Software for 3-Manifold Topology and Normal Surface Theory. http:\/\/regina.sourceforge.net\/."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627817.2627830"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(99)00258-7"},{"volume-title":"A Course in Simple Homotopy Theory","author":"Cohen M. M.","key":"e_1_2_1_15_1","unstructured":"M. M. Cohen. 1973. A Course in Simple Homotopy Theory. Springer, New York, NY."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90043-H"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"T. K. Dey H. Edelsbrunner and S. Guha. 1999. Computational topology. In Advances in Discrete and Computational Geometry. Contemporary mathematics Vol. 223. AMS 109--143.","DOI":"10.1090\/conm\/223\/03135"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","unstructured":"R. G. Downey M. R. Fellows B. Kapron M. Hallett and H. Wareham. 1994. The parameterized complexity of some problems in logic and linguistics. In Logical Foundations of Computer Science. Vol. 813. Springer 89--100.","DOI":"10.5555\/645681.664268"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","unstructured":"R. G. Downey and M. R. Fellows. 1999. Parameterized Complexity. Vol. 3. Springer New York NY.","DOI":"10.5555\/2464827"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","unstructured":"R. G. Downey and M. R. Fellows. 2013. Fundamentals of Parameterized Complexity. Springer New York NY.","DOI":"10.5555\/2568438"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1940475.1940516"},{"issue":"1","key":"e_1_2_1_22_1","first-page":"6","article-title":"simpcomp - a GAP package","volume":"2","author":"Effenberger F.","year":"2016","unstructured":"F. Effenberger and J. Spreer. 2016. simpcomp - a GAP package, Version 2.1.6. Retrieved February 5, 2016 from https:\/\/github.com\/simpcomp-team\/simpcomp.","journal-title":"Version"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(95)00015-1"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2008.24"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1006\/aima.1997.1650"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-09-00639-0"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0004-z"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00371-012-0726-8"},{"key":"e_1_2_1_30_1","volume-title":"Retrieved","author":"Hachimori M.","year":"2001","unstructured":"M. Hachimori. 2001. Simplicial complex library. Retrieved January 15, 2016 from http:\/\/infoshako.sk. tsukuba.ac.jp\/hachi\/math\/library\/. (2001)."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.4310\/jdg\/1090503053"},{"key":"e_1_2_1_32_1","series-title":"Lecture Notes in Mathematics","volume-title":"Simplicial Complexes of Graphs","author":"Jonsson J.","unstructured":"J. Jonsson. 2008. Simplicial Complexes of Graphs. In Lecture Notes in Mathematics. Springer Berlin Heidelberg."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.endm.2004.03.038"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480104445885"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0045375"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(03)00014-2"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1080\/10586458.2003.10504498"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2004.18"},{"key":"e_1_2_1_41_1","volume-title":"Lundell and Stephen Weingram","author":"Albert","year":"1969","unstructured":"Albert T. Lundell and Stephen Weingram. 1969. The Topology of CW--Complexes. Van Nostrand Reinhold, New York, NY."},{"key":"e_1_2_1_42_1","first-page":"97","article-title":"Combinatorial 3-manifolds with 10 vertices","volume":"49","author":"Lutz F.","year":"2008","unstructured":"F. Lutz. 2008. Combinatorial 3-manifolds with 10 vertices. Beitr\u00e4ge zur Algebra und Geometrie 49, 1, 97--106.","journal-title":"Beitr\u00e4ge zur Algebra und Geometrie"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","unstructured":"R. Malgouyres and A. Franc\u00e9s. 2008. Determining whether a simplicial 3-complex collapses to a 1-complex is NP-complete. In Discrete Geometry for Computer Imagery. Springer 177--188.","DOI":"10.5555\/1792454.1792474"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1215\/ijm\/1258130983"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2010.25"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.2307\/1969769"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(02)00771-9"},{"key":"e_1_2_1_48_1","first-page":"77","article-title":"The critical points of functions of n variables","volume":"33","author":"Morse M.","year":"1931","unstructured":"M. Morse. 1931. The critical points of functions of n variables. Transactions of the American Mathemational Society 33, 77--91.","journal-title":"Transactions of the American Mathemational Society"},{"key":"e_1_2_1_49_1","series-title":"Lecture Notes in Mathematics.","volume-title":"Seifert manifolds","author":"Orlik P.","unstructured":"P. Orlik. 1972. Seifert manifolds. In Lecture Notes in Mathematics. Vol. 291. Springer, Berlin."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.5555\/647680.732316"},{"key":"e_1_2_1_51_1","unstructured":"Georges Reeb. 1946. Sur les points singuliers d\u2019une forme de Pfaff compl\u00e8tement int\u00e9grable ou d\u2019une fonction num\u00e9rique. Comptes Rendus de L\u2019Acad\u00e9mie des Sciences de Paris 222 847--849."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2011.95"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1006\/jabr.1994.1191"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","unstructured":"A. Szymczak and J. Rossignac. 1999. Grow & fold: Compression of tetrahedral meshes. In Solid Modeling and Applications. ACM New York NY 54--64. 10.1145\/304012.304018","DOI":"10.1145\/304012.304018"},{"key":"e_1_2_1_56_1","unstructured":"Martin Tancer. 2011. Strong d-collapsibility. Contributions to Discrete Mathematics 6 2 32--35."},{"key":"e_1_2_1_57_1","unstructured":"M. Tancer. 2012. Recognition of collapsible complexes is NP-complete. arXiv:1211.6254 {cs.CG}."},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/321879.321884"},{"key":"e_1_2_1_59_1","unstructured":"T. van Dijk J.-P. van den Heuvel and W. Slob. 2006. Computing treewidth with LibTW. Retrieved from http:\/\/www.treewidth.com\/treewidth."},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1016\/0040-9383(63)90014-4"}],"container-title":["ACM Transactions on Mathematical Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2738034","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2738034","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:16:22Z","timestamp":1750227382000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2738034"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,3]]},"references-count":55,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,3]]}},"alternative-id":["10.1145\/2738034"],"URL":"https:\/\/doi.org\/10.1145\/2738034","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"type":"print","value":"0098-3500"},{"type":"electronic","value":"1557-7295"}],"subject":[],"published":{"date-parts":[[2016,3]]},"assertion":[{"value":"2014-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-02-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-03-01","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}