A permutation graph can be defined as an intersection graph of segments whose endpoints lie on two parallel lines ℓ 1 and ℓ 2 , one on each. A bipartite 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 n-vertex graph, whether we can remove at most k vertices to obtain a bipartite permutation graph. This problem is NP -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 O ( 9 k · n 9 ) , and also give a polynomial-time 9-approximation algorithm.

Faculty of Mathematics and Information Science Warsaw University of Technology Warsaw Poland

Faculty of Mathematics and Physics Charles University Prague Czech Republic

Faculty of Mathematics Informatics and Mechanics University of Warsaw Warsaw Poland

Theoretical Computer Science Department Faculty of Mathematics and Computer Science Jagiellonian University in Kraków Kraków Poland

Zobrazit více v PubMed

Baker KA, Fishburn PC, Roberts FS. Partial orders of dimension 2. Networks. 1972;2(1):11–28. doi: 10.1002/net.3230020103. DOI

Bożyk, L., Derbisz, J., Krawczyk, T., Novotná, 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–5:16. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, Germany (2020). 10.4230/LIPIcs.IPEC.2020.5. https://drops.dagstuhl.de/opus/volltexte/2020/13308

Brandstädt, A., Kratsch, D.: On the restriction of some

Cai L. Fixed-parameter tractability of graph modification problems for hereditary properties. Inf. Process. Lett. 1996;58(4):171–176. doi: 10.1016/0020-0190(96)00050-6. DOI

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–1115. SIAM (2016). 10.1137/1.9781611974331.ch77

Cao Y. Unit interval editing is fixed-parameter tractable. Inf. Comput. 2017;253:109–126. doi: 10.1016/j.ic.2017.01.008. DOI

Cao Y, Marx D. Chordal editing is fixed-parameter tractable. Algorithmica. 2016;75(1):118–137. doi: 10.1007/s00453-015-0014-x. DOI

Chudnovsky, M., Robertson, N., Seymour, P., Thomas, R.: The strong perfect graph theorem. Ann. Math. pp. 51–229 (2006)

Deogun JS, Steiner G. Polynomial algorithms for hamiltonian cycle in cocomparability graphs. SIAM J. Comput. 1994;23(3):520–552. doi: 10.1137/S0097539791200375. DOI

Derbisz, J.: A polynomial kernel for vertex deletion into bipartite permutation graphs. CoRR arXiv:2111.14005 (2021) PubMed PMC

Edmonds J, Karp RM. Theoretical improvements in algorithmic efficiency for network flow problems. J. ACM (JACM) 1972;19(2):248–264. doi: 10.1145/321694.321699. DOI

Gallai T. Transitiv orientierbare graphen. Acta Mathematica Academiae Scientiarum Hungarica. 1967;18(1–2):25–66. doi: 10.1007/BF02020961. DOI

Golumbic MC, Rotem D, Urrutia J. Comparability graphs and intersection graphs. Discret. Math. 1983;43(1):37–46. doi: 10.1016/0012-365X(83)90019-5. DOI

Grötschel, M., Lovász, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Algorithms and Combinatorics, vol. 2. Springer (1988). 10.1007/978-3-642-97881-4

Heggernes P, van ’t Hof P, Jansen BMP, Kratsch S, Villanger Y. Parameterized complexity of vertex deletion into perfect graph classes. Theor. Comput. Sci. 2013;511:172–180. doi: 10.1016/j.tcs.2012.03.013. DOI

Heggernes P, van ’t Hof P, Lokshtanov D, Nederlof J. Computing the cutwidth of bipartite permutation graphs in linear time. SIAM J. Discret. Math. 2012;26(3):1008–1021. doi: 10.1137/110830514. DOI

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–23:18. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany (2021). 10.4230/LIPIcs.IPEC.2021.23. https://drops.dagstuhl.de/opus/volltexte/2021/15406

Kelly D. The 3-irreducible partially ordered sets. Can. J. Math. 1977;29:367–383. doi: 10.4153/CJM-1977-040-3. DOI

Lekkeikerker C, Boland J. Representation of a finite graph by a set of intervals on the real line. Fundamenta Mathematicae. 1962;51(1):45–64. doi: 10.4064/fm-51-1-45-64. DOI

Lewis JM, Yannakakis M. The node-deletion problem for hereditary properties is DOI

Lokshtanov, D.: Wheel-free deletion is

Mancini, F.: Graph modification problems related to graph classes. PhD degree dissertation, University of Bergen Norway 2 (2008)

Marx D. Chordal deletion is fixed-parameter tractable. Algorithmica. 2010;57(4):747–768. doi: 10.1007/s00453-008-9233-8. DOI

Pnueli A, Lempel A, Even S. Transitive orientation of graphs and identification of permutation graphs. Can. J. Math. 1971;23(1):160–175. doi: 10.4153/CJM-1971-016-5. DOI

Spinrad JP, Brandstädt A, Stewart L. Bipartite permutation graphs. Discret. Appl. Math. 1987;18(3):279–292. doi: 10.1016/S0166-218X(87)80003-3. DOI

Trotter WT, Jr, Moore JI., Jr Characterization problems for graphs, partially ordered sets, lattices, and families of sets. Discret. Math. 1976;16(4):361–381. doi: 10.1016/S0012-365X(76)80011-8. DOI

van ’t Hof P, Villanger Y. Proper interval vertex deletion. Algorithmica. 2013;65(4):845–867. doi: 10.1007/s00453-012-9661-3. DOI

Villanger Y, Heggernes P, Paul C, Telle JA. Interval completion is fixed parameter tractable. SIAM J. Comput. 2009;38(5):2007–2020. doi: 10.1137/070710913. DOI

Vertex Deletion into Bipartite Permutation Graphs