{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,5]],"date-time":"2026-04-05T02:19:57Z","timestamp":1775355597555,"version":"3.50.1"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2022,2,1]],"date-time":"2022-02-01T00:00:00Z","timestamp":1643673600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,2,1]],"date-time":"2022-02-01T00:00:00Z","timestamp":1643673600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["714704"],"award-info":[{"award-number":["714704"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004281","name":"Polish National Science Centre","doi-asserted-by":"crossref","award":["2015\/17\/B\/ST6\/01873"],"award-info":[{"award-number":["2015\/17\/B\/ST6\/01873"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A permutation graph can be defined as an intersection graph of segments whose endpoints lie on two parallel lines <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\ell _1$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>\u2113<\/mml:mi>\n                    <mml:mn>1<\/mml:mn>\n                  <\/mml:msub>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\ell _2$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>\u2113<\/mml:mi>\n                    <mml:mn>2<\/mml:mn>\n                  <\/mml:msub>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, one on each. A\u00a0bipartite permutation graph is a permutation graph which is bipartite. In this paper we study the parameterized complexity of the bipartite permutation vertex deletion problem, which asks, for a given <jats:italic>n<\/jats:italic>-vertex graph, whether we can remove at most <jats:italic>k<\/jats:italic> vertices to obtain a bipartite permutation graph. This problem is <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathsf {NP}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>NP<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-complete by the classical result of Lewis and Yannakakis [20]. We analyze the structure of the so-called almost bipartite permutation graphs which may contain holes (large induced cycles) in contrast to bipartite permutation graphs. We exploit the structural properties of the shortest hole in a such graph. We use it to obtain an algorithm for the bipartite permutation vertex deletion problem with running time <jats:inline-formula><jats:alternatives><jats:tex-math>$${\\mathcal {O}}(9^k \\cdot n^9)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msup>\n                      <mml:mn>9<\/mml:mn>\n                      <mml:mi>k<\/mml:mi>\n                    <\/mml:msup>\n                    <mml:mo>\u00b7<\/mml:mo>\n                    <mml:msup>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mn>9<\/mml:mn>\n                    <\/mml:msup>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, and also give a polynomial-time 9-approximation algorithm.\n<\/jats:p>","DOI":"10.1007\/s00453-021-00923-7","type":"journal-article","created":{"date-parts":[[2022,2,1]],"date-time":"2022-02-01T07:03:12Z","timestamp":1643698992000},"page":"2271-2291","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Vertex Deletion into Bipartite Permutation Graphs"],"prefix":"10.1007","volume":"84","author":[{"given":"\u0141ukasz","family":"Bo\u017cyk","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jan","family":"Derbisz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tomasz","family":"Krawczyk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7955-4692","authenticated-orcid":false,"given":"Jana","family":"Novotn\u00e1","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1414-3507","authenticated-orcid":false,"given":"Karolina","family":"Okrasa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,2,1]]},"reference":[{"issue":"1","key":"923_CR1","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1002\/net.3230020103","volume":"2","author":"KA Baker","year":"1972","unstructured":"Baker, K.A., Fishburn, P.C., Roberts, F.S.: Partial orders of dimension 2. Networks 2(1), 11\u201328 (1972)","journal-title":"Networks"},{"key":"923_CR2","doi-asserted-by":"publisher","unstructured":"Bo\u017cyk, L., Derbisz, J., Krawczyk, T., Novotn\u00e1, J., Okrasa, K.: Vertex Deletion into Bipartite Permutation Graphs. In: 15th International Symposium on Parameterized and Exact Computation (IPEC 2020), Leibniz International Proceedings in Informatics (LIPIcs), vol. 180, pp. 5:1\u20135:16. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2020). https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2020.5. https:\/\/drops.dagstuhl.de\/opus\/volltexte\/2020\/13308","DOI":"10.4230\/LIPIcs.IPEC.2020.5"},{"key":"923_CR3","doi-asserted-by":"publisher","unstructured":"Brandst\u00e4dt, A., Kratsch, D.: On the restriction of some $$NP$$-complete graph problems to permutation graphs. In: Fundamentals of Computation Theory, FCT \u201985, Cottbus, GDR, September 9-13, 1985. Lecture Notes in Computer Science, vol. 199, pp. 53\u201362. Springer (1985). https:\/\/doi.org\/10.1007\/BFb0028791","DOI":"10.1007\/BFb0028791"},{"issue":"4","key":"923_CR4","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/0020-0190(96)00050-6","volume":"58","author":"L Cai","year":"1996","unstructured":"Cai, L.: Fixed-parameter tractability of graph modification problems for hereditary properties. Inf. Process. Lett. 58(4), 171\u2013176 (1996)","journal-title":"Inf. Process. Lett."},{"key":"923_CR5","doi-asserted-by":"publisher","unstructured":"Cao, Y.: Linear recognition of almost interval graphs. In: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pp. 1096\u20131115. SIAM (2016). https:\/\/doi.org\/10.1137\/1.9781611974331.ch77","DOI":"10.1137\/1.9781611974331.ch77"},{"key":"923_CR6","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/j.ic.2017.01.008","volume":"253","author":"Y Cao","year":"2017","unstructured":"Cao, Y.: Unit interval editing is fixed-parameter tractable. Inf. Comput. 253, 109\u2013126 (2017)","journal-title":"Inf. Comput."},{"issue":"1","key":"923_CR7","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1007\/s00453-015-0014-x","volume":"75","author":"Y Cao","year":"2016","unstructured":"Cao, Y., Marx, D.: Chordal editing is fixed-parameter tractable. Algorithmica 75(1), 118\u2013137 (2016)","journal-title":"Algorithmica"},{"key":"923_CR8","doi-asserted-by":"crossref","unstructured":"Chudnovsky, M., Robertson, N., Seymour, P., Thomas, R.: The strong perfect graph theorem. Ann. Math. pp. 51\u2013229 (2006)","DOI":"10.4007\/annals.2006.164.51"},{"issue":"3","key":"923_CR9","doi-asserted-by":"publisher","first-page":"520","DOI":"10.1137\/S0097539791200375","volume":"23","author":"JS Deogun","year":"1994","unstructured":"Deogun, J.S., Steiner, G.: Polynomial algorithms for hamiltonian cycle in cocomparability graphs. SIAM J. Comput. 23(3), 520\u2013552 (1994). https:\/\/doi.org\/10.1137\/S0097539791200375","journal-title":"SIAM J. Comput."},{"key":"923_CR10","unstructured":"Derbisz, J.: A polynomial kernel for vertex deletion into bipartite permutation graphs. CoRR arXiv:2111.14005 (2021)"},{"issue":"2","key":"923_CR11","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1145\/321694.321699","volume":"19","author":"J Edmonds","year":"1972","unstructured":"Edmonds, J., Karp, R.M.: Theoretical improvements in algorithmic efficiency for network flow problems. J. ACM (JACM) 19(2), 248\u2013264 (1972)","journal-title":"J. ACM (JACM)"},{"issue":"1\u20132","key":"923_CR12","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/BF02020961","volume":"18","author":"T Gallai","year":"1967","unstructured":"Gallai, T.: Transitiv orientierbare graphen. Acta Mathematica Academiae Scientiarum Hungarica 18(1\u20132), 25\u201366 (1967)","journal-title":"Acta Mathematica Academiae Scientiarum Hungarica"},{"issue":"1","key":"923_CR13","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/0012-365X(83)90019-5","volume":"43","author":"MC Golumbic","year":"1983","unstructured":"Golumbic, M.C., Rotem, D., Urrutia, J.: Comparability graphs and intersection graphs. Discret. Math. 43(1), 37\u201346 (1983). https:\/\/doi.org\/10.1016\/0012-365X(83)90019-5","journal-title":"Discret. Math."},{"key":"923_CR14","doi-asserted-by":"publisher","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Algorithms and Combinatorics, vol.\u00a02. Springer (1988). https:\/\/doi.org\/10.1007\/978-3-642-97881-4","DOI":"10.1007\/978-3-642-97881-4"},{"key":"923_CR15","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1016\/j.tcs.2012.03.013","volume":"511","author":"P Heggernes","year":"2013","unstructured":"Heggernes, P., van \u2019t Hof, P., Jansen, B.M.P., Kratsch, S., Villanger, Y.: Parameterized complexity of vertex deletion into perfect graph classes. Theor. Comput. Sci 511, 172\u2013180 (2013). https:\/\/doi.org\/10.1016\/j.tcs.2012.03.013","journal-title":"Theor. Comput. Sci"},{"issue":"3","key":"923_CR16","doi-asserted-by":"publisher","first-page":"1008","DOI":"10.1137\/110830514","volume":"26","author":"P Heggernes","year":"2012","unstructured":"Heggernes, P., van \u2019t Hof, P., Lokshtanov, D., Nederlof, J.: Computing the cutwidth of bipartite permutation graphs in linear time. SIAM J. Discret. Math. 26(3), 1008\u20131021 (2012). https:\/\/doi.org\/10.1137\/110830514","journal-title":"SIAM J. Discret. Math."},{"key":"923_CR17","doi-asserted-by":"publisher","unstructured":"Kanesh, L., Madathil, J., Sahu, A., Saurabh, S., Verma, S.: A Polynomial Kernel for Bipartite Permutation Vertex Deletion. In: Golovach, P.A., Zehavi, M. (eds.) 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), vol. 214, pp. 23:1\u201323:18. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2021). https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2021.23. https:\/\/drops.dagstuhl.de\/opus\/volltexte\/2021\/15406","DOI":"10.4230\/LIPIcs.IPEC.2021.23"},{"key":"923_CR18","doi-asserted-by":"publisher","first-page":"367","DOI":"10.4153\/CJM-1977-040-3","volume":"29","author":"D Kelly","year":"1977","unstructured":"Kelly, D.: The 3-irreducible partially ordered sets. Can. J. Math. 29, 367\u2013383 (1977)","journal-title":"Can. J. Math."},{"issue":"1","key":"923_CR19","doi-asserted-by":"publisher","first-page":"45","DOI":"10.4064\/fm-51-1-45-64","volume":"51","author":"C Lekkeikerker","year":"1962","unstructured":"Lekkeikerker, C., Boland, J.: Representation of a finite graph by a set of intervals on the real line. Fundamenta Mathematicae 51(1), 45\u201364 (1962)","journal-title":"Fundamenta Mathematicae"},{"issue":"2","key":"923_CR20","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/0022-0000(80)90060-4","volume":"20","author":"JM Lewis","year":"1980","unstructured":"Lewis, J.M., Yannakakis, M.: The node-deletion problem for hereditary properties is $$NP$$-complete. J. Comput. Syst. Sci. 20(2), 219\u2013230 (1980). https:\/\/doi.org\/10.1016\/0022-0000(80)90060-4","journal-title":"J. Comput. Syst. Sci."},{"key":"923_CR21","doi-asserted-by":"publisher","unstructured":"Lokshtanov, D.: Wheel-free deletion is $$W$$[2]-hard. In: Grohe, M., Niedermeier, R. (eds.) Parameterized and Exact Computation, Third International Workshop, IWPEC 2008, Victoria, Canada, May 14-16, 2008. Proceedings. Lecture Notes in Computer Science, vol. 5018, pp. 141\u2013147. Springer (2008). https:\/\/doi.org\/10.1007\/978-3-540-79723-4_14","DOI":"10.1007\/978-3-540-79723-4_14"},{"key":"923_CR22","unstructured":"Mancini, F.: Graph modification problems related to graph classes. PhD degree dissertation, University of Bergen Norway 2 (2008)"},{"issue":"4","key":"923_CR23","doi-asserted-by":"publisher","first-page":"747","DOI":"10.1007\/s00453-008-9233-8","volume":"57","author":"D Marx","year":"2010","unstructured":"Marx, D.: Chordal deletion is fixed-parameter tractable. Algorithmica 57(4), 747\u2013768 (2010). https:\/\/doi.org\/10.1007\/s00453-008-9233-8","journal-title":"Algorithmica"},{"issue":"1","key":"923_CR24","doi-asserted-by":"publisher","first-page":"160","DOI":"10.4153\/CJM-1971-016-5","volume":"23","author":"A Pnueli","year":"1971","unstructured":"Pnueli, A., Lempel, A., Even, S.: Transitive orientation of graphs and identification of permutation graphs. Can. J. Math. 23(1), 160\u2013175 (1971)","journal-title":"Can. J. Math."},{"issue":"3","key":"923_CR25","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1016\/S0166-218X(87)80003-3","volume":"18","author":"JP Spinrad","year":"1987","unstructured":"Spinrad, J.P., Brandst\u00e4dt, A., Stewart, L.: Bipartite permutation graphs. Discret. Appl. Math. 18(3), 279\u2013292 (1987). https:\/\/doi.org\/10.1016\/S0166-218X(87)80003-3","journal-title":"Discret. Appl. Math."},{"issue":"4","key":"923_CR26","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1016\/S0012-365X(76)80011-8","volume":"16","author":"WT Trotter Jr","year":"1976","unstructured":"Trotter, W.T., Jr., Moore, J.I., Jr.: Characterization problems for graphs, partially ordered sets, lattices, and families of sets. Discret. Math. 16(4), 361\u2013381 (1976). https:\/\/doi.org\/10.1016\/S0012-365X(76)80011-8","journal-title":"Discret. Math."},{"issue":"4","key":"923_CR27","doi-asserted-by":"publisher","first-page":"845","DOI":"10.1007\/s00453-012-9661-3","volume":"65","author":"P van\u00a0\u2019t Hof","year":"2013","unstructured":"van \u2019t Hof, P., Villanger, Y.: Proper interval vertex deletion. Algorithmica 65(4), 845\u2013867 (2013). https:\/\/doi.org\/10.1007\/s00453-012-9661-3","journal-title":"Algorithmica"},{"issue":"5","key":"923_CR28","doi-asserted-by":"publisher","first-page":"2007","DOI":"10.1137\/070710913","volume":"38","author":"Y Villanger","year":"2009","unstructured":"Villanger, Y., Heggernes, P., Paul, C., Telle, J.A.: Interval completion is fixed parameter tractable. SIAM J. Comput. 38(5), 2007\u20132020 (2009). https:\/\/doi.org\/10.1137\/070710913","journal-title":"SIAM J. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00923-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00923-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00923-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,21]],"date-time":"2022-07-21T13:10:34Z","timestamp":1658409034000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00923-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,1]]},"references-count":28,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2022,8]]}},"alternative-id":["923"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00923-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,2,1]]},"assertion":[{"value":"10 January 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 December 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 February 2022","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 that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}