Efficient Algorithms for Maximum Induced Matching Problem in Permutation and Trapezoid Graphs

• Autorzy: Nguyen Viet Dung , Pham Ba Thai , Do Phan Thuan

Identyfikatory

DOI

10.3233/FI-2021-2073

• Języki publikacji: EN

Abstrakty

EN

We first design an (n2) solution for finding a maximum induced matching in permutation graphs given their permutation models, based on a dynamic programming algorithm with the aid of the sweep line technique. With the support of the disjoint-set data structure, we improve the complexity to (m+n). Consequently, we extend this result to give an (m+n) algorithm for the same problem in trapezoid graphs. By combining our algorithms with the current best graph identification algorithms, we can solve the MIM problem in permutation and trapezoid graphs in linear and (n2) time, respectively. Our results are far better than the best known (mn) algorithm for the maximum induced matching problem in both graph classes, which was proposed by Habib et al.

Słowa kluczowe

EN

permutation graph; trapezoid graph; induced matching; sweep line; disjoint se

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2021
• Tom: Vol. 182, nr 3
• Strony: 257--283
• Opis fizyczny: Bibliogr. 32 poz., rys., ab., wyk.

Twórcy

autor

Nguyen Viet Dung

• Hanoi University of Science and Technology

autor

Pham Ba Thai

• Hanoi University of Science and Technology

autor

Do Phan Thuan

• Hanoi University of Science and Technology

Bibliografia

• [1] Dagan I, Golumbic MC, Pinter RY. Trapezoid graphs and their coloring. Discrete Applied Mathematics, 1988. 21(1):35-46. doi:10.1016/0166-218X(88)90032-7.
• [2] Golumbic MC. Algorithmic graph theory and perfect graphs. Elsevier, 2004.
• [3] Micali S, Vazirani VV. An O(√|V |.|E|) algorithm for finding maximum matching in general graphs. In: Foundations of Computer Science, 1980., 21st Annual Symposium on. IEEE, 1980 pp. 17-27. doi:10.1109/sfcs.1980.12.
• [4] Surynek P. Compact representations of cooperative path-finding as SAT based on matchings in bipartite graphs. In: Tools with Artificial Intelligence (ICTAI), 2014 IEEE 26th International Conference on. IEEE, 2014 pp. 875-882. doi:10.1109/ictai.2014.134.
• [5] Kocaoglu M, Shanmugam K, Bareinboim E. Experimental design for learning causal graphs with latent variables. In: Advances in Neural Information Processing Systems. 2017 pp. 7018-7028. doi:10.5555/3295222.3295445.
• [6] Golumbic MC, Lewenstein M. New results on induced matchings. Discrete Applied Mathematics, 2000. 101(1-3):157-165. doi:10.1016/S0166-218X(99)00194-8.
• [7] Stockmeyer LJ, Vazirani VV. NP-completeness of some generalizations of the maximum matching problem. Information Processing Letters, 1982. 15(1):14-19. doi:10.1016/0020-0190(82)90077-1.
• [8] Chang MS, Chen LH, Hung LJ. Moderately exponential time algorithms for the maximum induced matching problem. Optimization Letters, 2015. 9(5):981-998. doi:10.1007/s11590-014-0813-z.
• [9] Xiao M, Tan H. Exact algorithms for Maximum Induced Matching. Information and Computation, 2017. 256:196-211. doi:10.1016/j.ic.2017.07.006.V.D. Nguyen et al. / Maximum Induced Matching in Permutation and Trapezoid Graphs 277
• [10] Golumbic MC, Laskar RC. Irredundancy in circular arc graphs. Discrete Applied Mathematics, 1993. 44(1-3):79-89. doi:10.1016/0166-218X(93)90223-B.
• [11] Cameron K. Induced matchings. Discrete Applied Mathematics, 1989. 24(1-3):97-102. doi:10.1016/0166-218X(92)90275-F.
• [12] Pandey A, Panda B, Dane P, Kashyap M. Induced matching in some subclasses of bipartite graphs. In: Conference on Algorithms and Discrete Applied Mathematics. Springer, 2017 pp. 308-319. doi:10.1007/978-3-319-53007-9.
• [13] K¨ohler EG. Graphs without asteroidal triples. Cuvillier, 1999.
• [14] Erveˇs R, ˇSparl P. Maximum Induced Matching of Hexagonal Graphs. Bulletin of the Malaysian Mathematical Sciences Society, 2016. 39(1):283-295. doi:10.1007/s40840-015-0288-9.
• [15] Brandst¨adt A, Ho`ang CT. Maximum induced matchings for chordal graphs in linear time. Algorithmica, 2008. 52(4):440-447. doi:10.1007/s00453-007-9045-2.
• [16] Cameron K, Sritharan R, Tang Y. Finding a maximum induced matching in weakly chordal graphs. Discrete Mathematics, 2003. 266(1-3):133-142. doi:10.1016/S0012-365X(02)00803-8.
• [17] Broersma H, Kloks T, Kratsch D, M¨uller H. Independent sets in asteroidal triple-free graphs. SIAM Journal on Discrete Mathematics, 1999. 12(2):276-287. doi:10.1137/S0895480197326346.
• [18] Chang JM. Induced matchings in asteroidal triple-free graphs. Discrete Applied Mathematics, 2003. 132(1-3):67-78. doi:10.1016/S0166-218X(03)00390-1.
• [19] Do PT, Le NK, Vu VT. Efficient maximum matching algorithms for trapezoid graphs. Electronic Journal of Graph Theory and Applications, 2017. 5(1):7-20. doi:10.5614/ejgta.2017.5.1.2.
• [20] Rhee C, Liang YD. Finding a maximum matching in a permutation graph. Acta informatica, 1995. 32(8):779-792. doi:10.1007/bf01178659.
• [21] Habib M, Mouatadid L. Maximum induced matching algorithms via vertex ordering characterizations. Algorithmica, 2020. 82(2):260-278. doi:10.1007/s00453-018-00538-5.
• [22] Nguyen VD, Pham BT, Tran VH, Do PT. A dynamic programming algorithm for the maximum induced matching problem in permutation graphs. In: Proceedings of the Ninth International Symposium on Information and Communication Technology. ACM, 2018 pp. 92-97. doi:10.1145/3287921.3287961.
• [23] Nguyen VD, Do PT. Quadratic time algorithm for maximum induced matching problem in trapezoid graphs. In: Proceedings of the 2019 2nd International Conference on Information Science and Systems. ACM, 2019 pp. 185-189. doi:10.1145/3322645.3322653.
• [24] Felsner S, M¨uller R, Wernisch L. Trapezoid graphs and generalizations, geometry and algorithms. Discrete Applied Mathematics, 1997. 74(1):13-32. doi:10.1016/S0166-218X(96)00013-3.
• [25] Bentley JL. Algorithms for Klee’s rectangle problems. Technical report, Technical Report, Computer, 1977.
• [26] van Emde Boas P. Preserving order in a forest in less than logarithmic time and linear space. Information processing letters, 1977. 6(3):80-82. doi:10.1016/0020-0190(77)90031-X.
• [27] Gabow HN, Tarjan RE. A linear-time algorithm for a special case of disjoint set union. Journal of
• computer and system sciences, 1985. 30(2):209-221.
• [28] McConnell RM, Spinrad JP. Modular decomposition and transitive orientation. Discrete Mathematics, 1999. 201(1-3):189-241. doi:10.1016/S0012-365X(98)00319-7.
• [29] Cogis O. On the Ferrers dimension of a digraph. Discrete Mathematics, 1982. 38(1):47-52. doi:10.1016/0012-365X(82)90167-4.
• [30] Ma TH, Spinrad JP. On the 2-chain subgraph cover and related problems. Journal of Algorithms, 1994. 17(2):251-268. doi:10.1006/jagm.1994.1034.
• [31] Ma Th. Algorithms on special classes of graphs and partially ordered sets. Vanderbilt University, 1990.
• [32] Ma TH, Spinrad JP. Avoiding matrix multiplication. In: International Workshop on Graph-Theoretic Concepts in Computer Science. Springer, 1990 pp. 61-71. doi:10.1007/3-540-53832-1.

Uwagi

Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023). (PL)