{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T20:56:58Z","timestamp":1775595418156,"version":"3.50.1"},"reference-count":56,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2022,7,31]],"date-time":"2022-07-31T00:00:00Z","timestamp":1659225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ANR","award":["DEMOGRAPH ANR-16-CE40-0028, ESIGMA ANR-17-CE23-0010, ELIT ANR-20-CE48-0008, UTMA ANR-20-CE92-0027"],"award-info":[{"award-number":["DEMOGRAPH ANR-16-CE40-0028, ESIGMA ANR-17-CE23-0010, ELIT ANR-20-CE48-0008, UTMA ANR-20-CE92-0027"]}]},{"name":"French Ministry of Europe and Foreign Affairs"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2022,7,31]]},"abstract":"<jats:p>\n            Let \ud835\udca2 be a minor-closed graph class. We say that a graph\n            <jats:italic>G<\/jats:italic>\n            is a\n            <jats:italic>\n              <jats:italic>k<\/jats:italic>\n              -apex\n            <\/jats:italic>\n            of\n            <jats:italic>\ud835\udca2<\/jats:italic>\n            if\n            <jats:italic>G<\/jats:italic>\n            contains a set\n            <jats:italic>S<\/jats:italic>\n            of at most\n            <jats:italic>k<\/jats:italic>\n            vertices such that G\\S belongs to\n            <jats:italic>\ud835\udca2<\/jats:italic>\n            . We denote by\n            <jats:italic>\ud835\udc9c<\/jats:italic>\n            <jats:sub>\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sub>\n            (\n            <jats:italic>\ud835\udca2<\/jats:italic>\n            ) the set of all graphs that are\n            <jats:italic>k<\/jats:italic>\n            -apices of\n            <jats:italic>\ud835\udca2<\/jats:italic>\n            . In the first paper of this series, we obtained upper bounds on the size of the graphs in the minor-obstruction set of\n            <jats:italic>\ud835\udc9c<\/jats:italic>\n            <jats:sub>k<\/jats:sub>\n            (\n            <jats:italic>\ud835\udca2<\/jats:italic>\n            ), i.e., the minor-minimal set of graphs not belonging to\n            <jats:italic>\ud835\udc9c<\/jats:italic>\n            <jats:sub>k<\/jats:sub>\n            (\n            <jats:italic>\ud835\udca2<\/jats:italic>\n            ). In this article, we provide an algorithm that, given a graph\n            <jats:italic>G<\/jats:italic>\n            on\n            <jats:italic>n<\/jats:italic>\n            vertices, runs in time 2\n            <jats:sup>\n              <jats:sans-serif>poly<\/jats:sans-serif>\n              <jats:italic>(k)<\/jats:italic>\n            <\/jats:sup>\n            \u22c5\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>3<\/jats:sup>\n            and either returns a set\n            <jats:italic>S<\/jats:italic>\n            certifying that\n            <jats:italic>G<\/jats:italic>\n            \u2208\n            <jats:italic>\n              \ud835\udc9c\n              <jats:sub>k<\/jats:sub>\n            <\/jats:italic>\n            (\n            <jats:italic>\ud835\udca2<\/jats:italic>\n            ), or reports that\n            <jats:italic>\n              G \u2209 \ud835\udc9c\n              <jats:sub>k<\/jats:sub>\n            <\/jats:italic>\n            (\n            <jats:italic>\ud835\udca2<\/jats:italic>\n            ). Here\n            <jats:sans-serif>poly<\/jats:sans-serif>\n            is a polynomial function whose degree depends on the maximum size of a minor-obstruction of\n            <jats:italic>\ud835\udca2<\/jats:italic>\n            . In the special case where \ud835\udca2 excludes some apex graph as a minor, we give an alternative algorithm running in 2\n            <jats:sup>\n              <jats:sans-serif>poly<\/jats:sans-serif>\n              <jats:italic>(k)<\/jats:italic>\n            <\/jats:sup>\n            \u22c5\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            -time.\n          <\/jats:p>","DOI":"10.1145\/3519028","type":"journal-article","created":{"date-parts":[[2022,3,7]],"date-time":"2022-03-07T13:43:07Z","timestamp":1646660587000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["<i>k<\/i>\n            -apices of Minor-closed Graph Classes. II. Parameterized Algorithms"],"prefix":"10.1145","volume":"18","author":[{"given":"Ignasi","family":"Sau","sequence":"first","affiliation":[{"name":"LIRMM, Universit\u00e9 de Montpellier, CNRS, Montpellier, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4175-7793","authenticated-orcid":false,"given":"Giannos","family":"Stamoulis","sequence":"additional","affiliation":[{"name":"LIRMM, Universit\u00e9 de Montpellier, CNRS, Montpellier, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dimitrios M.","family":"Thilikos","sequence":"additional","affiliation":[{"name":"LIRMM, Universit\u00e9 de Montpellier, CNRS, Montpellier, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,10,11]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.09.015"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.5555\/1347082.1347153"},{"key":"e_1_3_2_4_2","doi-asserted-by":"crossref","unstructured":"Ernst Althaus and Sarah Ziegler. 2019. Optimal tree decompositions revisited: A simpler linear-time FPT algorithm. arXiv:1912.09144. Retrieved from https:\/\/arxiv.org\/abs\/1912.09144.","DOI":"10.1007\/978-3-030-63072-0_6"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1137\/0608024"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.57"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1137\/19M1287146"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2020.01.026"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2019.11.002"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1137\/130947374"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.4230\/DagRep.4.2.38"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2017.10.018"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190110111"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.06.026"},{"key":"e_1_3_2_15_2","unstructured":"Christophe Crespelle P\u00e5l Gr\u00f8n\u00e5s Drange Fedor V. Fomin and Petr A. Golovach. 2013. A survey of parameterized algorithms and the complexity of edge modification. arXiv:2001.06867. Retrieved from https:\/\/arxiv.org\/abs\/2001.06867."},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-011-9578-2"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53622-3"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01190507"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/44483.44491"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-29953-X"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.STACS.2019.28"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.62"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384318"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-19647-3_1"},{"key":"e_1_3_2_27_2","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey Michael R.","year":"1979","unstructured":"Michael R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman."},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/3029051"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.130"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1137\/120883736"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.45"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2019.07.007"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2017.09.006"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806784"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/2797140"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ISAAC.2018.20"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2014.05.001"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-019-00592-7"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579141"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90060-4"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-79723-4_14"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9484-z"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1093\/ACPROF:OSO\/9780198566076.001.0001"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054100000247"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2003.10.009"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1006"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2004.08.001"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2008.08.003"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2007.12.007"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1994.1073"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2020.95"},{"key":"e_1_3_2_53_2","unstructured":"Ignasi Sau Giannos Stamoulis and Dimitrios M. Thilikos. 2021. A more accurate view of the flat wall theorem. arXiv:2102.06463. Retrieved from https:\/\/arxiv.org\/abs\/2102.06463."},{"key":"e_1_3_2_54_2","unstructured":"Ignasi Sau Giannos Stamoulis and Dimitrios M. Thilikos. 2021. k -apices of minor-closed graph classes. I. Bounding the obstructions. arXiv:2103.00882. Retrieved from https:\/\/arxiv.org\/abs\/2103.00882."},{"key":"e_1_3_2_55_2","volume-title":"Graph Modification Problems and Their Applications to Genomic Research","author":"Sharan Roded","year":"2002","unstructured":"Roded Sharan. 2002. Graph Modification Problems and Their Applications to Genomic Research. Ph.D. Dissertation. Sackler Faculty of Exact Sciences, School of Computer Science."},{"key":"e_1_3_2_56_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-30891-8_13"},{"key":"e_1_3_2_57_2","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.2000.2013"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519028","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3519028","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:12:20Z","timestamp":1750191140000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519028"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,31]]},"references-count":56,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,7,31]]}},"alternative-id":["10.1145\/3519028"],"URL":"https:\/\/doi.org\/10.1145\/3519028","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,7,31]]},"assertion":[{"value":"2021-03-02","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-02-14","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-10-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}