{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,24]],"date-time":"2026-06-24T01:46:57Z","timestamp":1782265617941,"version":"3.54.5"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2026,5,20]],"date-time":"2026-05-20T00:00:00Z","timestamp":1779235200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,5,20]],"date-time":"2026-05-20T00:00:00Z","timestamp":1779235200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100000275","name":"Leverhulme Trust","doi-asserted-by":"publisher","award":["RPG-2016-258"],"award-info":[{"award-number":["RPG-2016-258"]}],"id":[{"id":"10.13039\/501100000275","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["714704"],"award-info":[{"award-number":["714704"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-16-CE40-0028"],"award-info":[{"award-number":["ANR-16-CE40-0028"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003725","name":"National Research Foundation of Korea","doi-asserted-by":"publisher","award":["NRF-2021K2A9A2A11101617"],"award-info":[{"award-number":["NRF-2021K2A9A2A11101617"]}],"id":[{"id":"10.13039\/501100003725","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100010446","name":"Institute for Basic Science","doi-asserted-by":"publisher","award":["IBS-R029-C1"],"award-info":[{"award-number":["IBS-R029-C1"]}],"id":[{"id":"10.13039\/501100010446","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2026,6]]},"DOI":"10.1007\/s00453-026-01393-5","type":"journal-article","created":{"date-parts":[[2026,5,20]],"date-time":"2026-05-20T07:36:36Z","timestamp":1779262596000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Computing Pivot-Minors"],"prefix":"10.1007","volume":"88","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9515-6945","authenticated-orcid":false,"given":"Konrad K.","family":"Dabrowski","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0535-9640","authenticated-orcid":false,"given":"Fran\u00e7ois","family":"Dross","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3614-4199","authenticated-orcid":false,"given":"Jisu","family":"Jeong","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1838-7744","authenticated-orcid":false,"given":"Mamadou Moustapha","family":"Kant\u00e9","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1820-1962","authenticated-orcid":false,"given":"O-joung","family":"Kwon","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6889-7286","authenticated-orcid":false,"given":"Sang-il","family":"Oum","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5945-9287","authenticated-orcid":false,"given":"Dani\u00ebl","family":"Paulusma","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,5,20]]},"reference":[{"key":"1393_CR1","unstructured":"Aboulker, P., Bonnet, \u00c9., Picavet, T., Trotignon, N.: Induced disjoint paths without an induced minor. In 52nd International Colloquium on Automata, Languages, and Programming, volume 334 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 4, 14. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, (2025)"},{"issue":"1","key":"1393_CR2","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1016\/0095-8956(88)90055-X","volume":"45","author":"A Bouchet","year":"1988","unstructured":"Bouchet, A.: Graphic presentations of isotropic systems. J. Comb. Theory Ser. B 45(1), 58\u201376 (1988)","journal-title":"J. Comb. Theory Ser. B"},{"key":"1393_CR3","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1006\/jctb.1994.1008","volume":"60","author":"A Bouchet","year":"1994","unstructured":"Bouchet, A.: Circle graph obstructions. J. Comb. Theory Ser. B 60, 107\u2013144 (1994)","journal-title":"J. Comb. Theory Ser. B"},{"key":"1393_CR4","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/0024-3795(91)90020-W","volume":"146","author":"A Bouchet","year":"1991","unstructured":"Bouchet, A., Duchamp, A.: Representability of $$\\Delta $$-matroids over $${\\rm GF}(2)$$. Linear Algebra Appl. 146, 67\u201378 (1991)","journal-title":"Linear Algebra Appl."},{"key":"1393_CR5","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1002\/jgt.3190110111","volume":"11","author":"AE Brouwer","year":"1987","unstructured":"Brouwer, A.E., Veldman, H.J.: Contractibility and NP-completeness. J. Graph Theory 11, 71\u201379 (1987)","journal-title":"J. Graph Theory"},{"key":"1393_CR6","doi-asserted-by":"crossref","unstructured":"Chudnovsky, M., Scott, A., Seymour, P.D., Spirkl, S.: Detecting an odd hole. Journal of the ACM, 67:5:1\u20135:12, (2020)","DOI":"10.1145\/3375720"},{"key":"1393_CR7","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/0166-218X(81)90013-5","volume":"3","author":"DG Corneil","year":"1981","unstructured":"Corneil, D.G., Lerchs, H., Burlingham, L.S.: Complement reducible graphs. Discret. Appl. Math. 3, 163\u2013174 (1981)","journal-title":"Discret. Appl. Math."},{"key":"1393_CR8","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/j.jctb.2006.04.003","volume":"97","author":"B Courcelle","year":"2007","unstructured":"Courcelle, B., Oum, S.: Vertex-minors, monadic second-order logic, and a conjecture by Seese. J. Comb. Theory Ser. B 97, 91\u2013126 (2007)","journal-title":"J. Comb. Theory Ser. B"},{"key":"1393_CR9","doi-asserted-by":"publisher","first-page":"2922","DOI":"10.1137\/21M1402339","volume":"35","author":"KK Dabrowski","year":"2021","unstructured":"Dabrowski, K.K., Dross, F., Jeong, J., Kant\u00e9, M.M., Kwon, O., Oum, S., Paulusma, D.: Tree pivot-minors and linear rank-width. SIAM J. Discret. Math. 35, 2922\u20132945 (2021)","journal-title":"SIAM J. Discret. Math."},{"key":"1393_CR10","doi-asserted-by":"crossref","unstructured":"Dabrowski, K.K., Dross, F., Jeong, J., Kant\u00e9, M.M., Kwon, O., Oum, S., Paulusma, D.: Computing small pivot-minors. In Proceedings of the 44th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2018, volume 11159 of Lecture Notes in Computer Science, pages 125\u2013138. Springer, Heidelberg, (2018)","DOI":"10.1007\/978-3-030-00256-5_11"},{"key":"1393_CR11","doi-asserted-by":"publisher","first-page":"106222","DOI":"10.1016\/j.ipl.2021.106222","volume":"175","author":"A Dahlberg","year":"2022","unstructured":"Dahlberg, A., Helsen, J., Wehner, S.: The complexity of the vertex-minor problem. Inf. Process. Lett. 175, 106222 (2022)","journal-title":"Inf. Process. Lett."},{"key":"1393_CR12","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1007\/BF01190507","volume":"13","author":"MR Fellows","year":"1995","unstructured":"Fellows, M.R., Kratochv\u00edl, J., Middendorf, M., Pfeiffer, F.: The complexity of induced minors and related problems. Algorithmica 13, 266\u2013282 (1995)","journal-title":"Algorithmica"},{"key":"1393_CR13","unstructured":"Fon-der Flaass, D.G.: On local complementations of graphs. In Combinatorics (Eger, 1987), volume\u00a052 of Colloq. Math. Soc. J\u00e1nos Bolyai, pages 257\u2013266. North-Holland, Amsterdam, (1988)"},{"key":"1393_CR14","doi-asserted-by":"publisher","first-page":"704","DOI":"10.1137\/0205049","volume":"5","author":"MR Garey","year":"1976","unstructured":"Garey, M.R., Johnson, D.S., Tarjan, R.E.: The planar Hamiltonian circuit problem is NP-complete. SIAM J. Comput. 5, 704\u2013714 (1976)","journal-title":"SIAM J. Comput."},{"key":"1393_CR15","doi-asserted-by":"crossref","unstructured":"Geelen, J., Gerards, B., Whittle, G.: Towards a structure theory for matrices and matroids. In International Congress of Mathematicians. Vol. III, pages 827\u2013842. European Mathematical Society, Z\u00fcrich, (2006)","DOI":"10.4171\/022-3\/41"},{"key":"1393_CR16","doi-asserted-by":"crossref","unstructured":"Geelen, J., Kwon, O., McCarty, R., Wollan, P.: The grid theorem for vertex-minors. J. Comb. Theory Ser. B 158, 93\u201316 (2023)","DOI":"10.1016\/j.jctb.2020.08.004"},{"key":"1393_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1002\/jgt.20363","volume":"61","author":"J Geelen","year":"2009","unstructured":"Geelen, J., Oum, S.: Circle graph obstructions under pivoting. J. Graph Theory 61, 1\u201311 (2009)","journal-title":"J. Graph Theory"},{"key":"1393_CR18","doi-asserted-by":"crossref","unstructured":"Grohe, M., Kawarabayashi, K.-I., Marx, D., Wollan, P.: Finding topological subgraphs is fixed-parameter tractable. In Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, pages 479\u2013488. ACM, New York, (2011)","DOI":"10.1145\/1993636.1993700"},{"key":"1393_CR19","doi-asserted-by":"crossref","unstructured":"Kant\u00e9, M.M., Kwon, O.: Linear rank-width of distance-hereditary graphs II. Vertex-minor obstructions. Eur. J. Comb. 74, 110\u2013139 (2018)","DOI":"10.1016\/j.ejc.2018.07.009"},{"key":"1393_CR20","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1016\/j.dam.2024.03.011","volume":"351","author":"D Kim","year":"2024","unstructured":"Kim, D., Oum, S.: Vertex-minors of graphs: A survey. Discret. Appl. Math. 351, 54\u201373 (2024)","journal-title":"Discret. Appl. Math."},{"key":"1393_CR21","doi-asserted-by":"crossref","unstructured":"Korhonen, T., Lokshtanov, D.: Induced-minor-free graphs: separator theorem, subexponential algorithms, and improved hardness of recognition. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 5249\u20135275. SIAM, Philadelphia, PA, (2024)","DOI":"10.1137\/1.9781611977912.188"},{"key":"1393_CR22","doi-asserted-by":"crossref","unstructured":"Korhonen, T., Pilipczuk, M., Stamoulis, G.: Minor Containment and Disjoint Paths in Almost-Linear Time. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pages 53\u201361, Los Alamitos, CA, USA, October 2024. IEEE Computer Society","DOI":"10.1109\/FOCS61266.2024.00014"},{"key":"1393_CR23","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1016\/j.jctb.2021.01.005","volume":"149","author":"O Kwon","year":"2021","unstructured":"Kwon, O., McCarty, R., Oum, S., Wollan, P.: Obstructions for bounded shrub-depth and rank-depth. J. Comb. Theory Ser. B 149, 76\u201391 (2021)","journal-title":"J. Comb. Theory Ser. B"},{"key":"1393_CR24","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1016\/j.dam.2013.01.007","volume":"168","author":"O Kwon","year":"2014","unstructured":"Kwon, O., Oum, S.: Graphs of small rank-width are pivot-minors of graphs of small tree-width. Discret. Appl. Math. 168, 108\u2013118 (2014)","journal-title":"Discret. Appl. Math."},{"key":"1393_CR25","doi-asserted-by":"publisher","first-page":"3540","DOI":"10.1016\/j.dam.2009.02.015","volume":"157","author":"B L\u00e9v\u00eaque","year":"2009","unstructured":"L\u00e9v\u00eaque, B., Lin, D.Y., Maffray, F., Trotignon, N.: Detecting induced subgraphs. Discret. Appl. Math. 157, 3540\u20133551 (2009)","journal-title":"Discret. Appl. Math."},{"key":"1393_CR26","doi-asserted-by":"publisher","first-page":"924","DOI":"10.1016\/j.jctb.2012.04.005","volume":"102","author":"B L\u00e9v\u00eaque","year":"2012","unstructured":"L\u00e9v\u00eaque, B., Maffray, F., Trotignon, N.: On graphs with no induced subdivision of $$K_4$$. J. Comb. Theory Ser. B 102, 924\u2013947 (2012)","journal-title":"J. Comb. Theory Ser. B"},{"key":"1393_CR27","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1016\/0012-365X(92)90687-B","volume":"108","author":"J Matou\u0161ek","year":"1992","unstructured":"Matou\u0161ek, J., Thomas, R.: On the complexity of finding iso- and other morphisms for partial $$k$$-trees. Discret. Math. 108, 343\u2013364 (1992)","journal-title":"Discret. Math."},{"key":"1393_CR28","doi-asserted-by":"crossref","unstructured":"McConnell, R.M., Mehlhorn, K., N\u00e4her, S., Schweitzer, P.: Survey: Certifying algorithms. Computer Science Review 5, 119\u2013161 (2011)","DOI":"10.1016\/j.cosrev.2010.09.009"},{"key":"1393_CR29","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/j.jctb.2005.03.003","volume":"95","author":"S Oum","year":"2005","unstructured":"Oum, S.: Rank-width and vertex-minors. J. Comb. Theory Ser. B 95, 79\u2013100 (2005)","journal-title":"J. Comb. Theory Ser. B"},{"key":"1393_CR30","doi-asserted-by":"publisher","first-page":"666","DOI":"10.1137\/050629616","volume":"22","author":"S Oum","year":"2008","unstructured":"Oum, S.: Rank-width and well-quasi-ordering. SIAM J. Discret. Math. 22, 666\u2013682 (2008)","journal-title":"SIAM J. Discret. Math."},{"key":"1393_CR31","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1002\/jgt.20353","volume":"60","author":"S Oum","year":"2009","unstructured":"Oum, S.: Excluding a bipartite circle graph from line graphs. J. Graph Theory 60, 183\u2013203 (2009)","journal-title":"J. Graph Theory"},{"key":"1393_CR32","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/j.dam.2016.08.006","volume":"231","author":"S Oum","year":"2017","unstructured":"Oum, S.: Rank-width: Algorithmic and structural results. Discret. Appl. Math. 231, 15\u201324 (2017)","journal-title":"Discret. Appl. Math."},{"key":"1393_CR33","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1016\/j.jctb.2005.10.006","volume":"96","author":"S Oum","year":"2006","unstructured":"Oum, S., Seymour, P.: Approximating clique-width and branch-width. J. Comb. Theory Ser. B 96, 514\u2013528 (2006)","journal-title":"J. Comb. Theory Ser. B"},{"key":"1393_CR34","doi-asserted-by":"crossref","unstructured":"Oxley, J.: Matroid Theory, volume\u00a021 of Oxford Graduate Texts in Mathematics. Oxford University Press, Oxford, second edition, (2011)","DOI":"10.1093\/acprof:oso\/9780198566946.001.0001"},{"key":"1393_CR35","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1006\/jctb.1995.1006","volume":"63","author":"N Robertson","year":"1995","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XIII. The disjoint paths problem. J. Comb. Theory Ser. B 63, 65\u2013110 (1995)","journal-title":"J. Comb. Theory Ser. B"},{"key":"1393_CR36","doi-asserted-by":"crossref","first-page":"799","DOI":"10.1016\/j.dam.2010.05.005","volume":"160","author":"On graph contractions and induced minors","year":"2012","unstructured":"On graph contractions and induced minors: van \u2019t Hof, P., Kami\u0144ski, M., Paulusma, D., Szeider, S., Thilikos, D.M. Discret. Appl. Math. 160, 799\u2013809 (2012)","journal-title":"Discret. Appl. Math."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-026-01393-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-026-01393-5","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-026-01393-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,24]],"date-time":"2026-06-24T01:11:09Z","timestamp":1782263469000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-026-01393-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,20]]},"references-count":36,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,6]]}},"alternative-id":["1393"],"URL":"https:\/\/doi.org\/10.1007\/s00453-026-01393-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,20]]},"assertion":[{"value":"8 November 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 April 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 May 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing Interests"}}],"article-number":"47"}}