Abstract
Given a graph G, Min-Max-Acy-Matching is the problem of finding a maximal matching M in G of minimum cardinality such that the set of M-saturated vertices induces an acyclic subgraph in G. The decision version of Min-Max-Acy-Matching is known to be \(\textsf{NP}\)-complete even for planar perfect elimination bipartite graphs. In this paper, we give the first positive algorithmic result for Min-Max-Acy-Matching by presenting a linear-time algorithm for computing a minimum cardinality maximal acyclic matching in proper interval graphs.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Let \(K_{n}\) and \(P_{n}\) denote a complete graph and a path graph on n vertices, respectively.
References
Bazgan, C., et al.: The many facets of upper domination. Theor. Comput. Sci. 717, 2–25 (2018)
Boria, N., Croce, F.D., Paschos, V.T.: On the max min vertex cover problem. Discret. Appl. Math. 196, 62–71 (2015)
Chaudhary, J., Mishra, S., Panda, B.S.: On the complexity of minimum maximal acyclic matching. In: Proceedings of the 28th International Computing and Combinatorics Conference (COCOON) (to appear)
Chaudhary, J., Panda, B.S.: On the complexity of minimum maximal uniquely restricted matching. Theor. Comput. Sci. 882, 15–28 (2021)
Damaschke, P.: Parameterized algorithms for double hypergraph dualization with rank limitation and maximum minimal vertex cover. Discret. Optim. 8(1), 18–24 (2011)
Dublois, L., Hanaka, T., Ghadikolaei, M.K., Lampis, M., Melissinos, N.: (In)approximability of maximum minimal FVS. In: Proceedings of the 31st International Symposium on Algorithms and Computation (ISAAC), Leibniz International Proceedings in Informatics, vol. 181, pp. 3:1–14 (2020)
Goddard, W., Hedetniemi, S.M., Hedetniemi, S.T., Laskar, R.: Generalized subgraph-restricted matchings in graphs. Discret. Math. 293(1–3), 129–138 (2005)
Jamison, R.E., Laskar, R.: Elimination orderings of chordal graphs. In: Proceedings of the Seminar on Combinatorics and Applications, pp. 192–200 (1982)
Lepin, V.V.: A linear algorithm for computing of a minimum weight maximal induced matching in an edge-weighted tree. Electron. Notes Discret. Math. 24, 111–116 (2006)
Orlovich, Y.L., Finke, G., Gordon, V., Zverovich, I.: Approximability results for the maximum and minimum maximal induced matching problems. Discret. Optim. 5(3), 584–593 (2008)
Orlovich, Y. L., Zverovich, I. E.: Maximal induced matchings of minimum/ maximum size. Technical report, DIMACS TR 2004–26 (2004)
Panda, B.S., Chaudhary, J.: Acyclic matching in some subclasses of graphs. In: Gasieniec, L., Klasing, R., Radzik, T. (eds.) IWOCA 2020. LNCS, vol. 12126, pp. 409–421. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-48966-3_31
Panda, B.S., Das, S.K.: A linear time recognition algorithm for proper interval graphs. Inf. Process. Lett. 87(3), 153–161 (2003)
Panda, B.S., Pandey, A.: On the complexity of minimum cardinality maximal uniquely restricted matching in graphs. In: Arumugam, S., Bagga, J., Beineke, L.W., Panda, B.S. (eds.) ICTCSDM 2016. LNCS, vol. 10398, pp. 218–227. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-64419-6_29
Yannakakis, M., Gavril, F.: Edge dominating sets in graphs. SIAM J. Appl. Math. 38(3), 364–372 (1980)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Chaudhary, J., Mishra, S., Panda, B.S. (2023). Minimum Maximal Acyclic Matching in Proper Interval Graphs. In: Bagchi, A., Muthu, R. (eds) Algorithms and Discrete Applied Mathematics. CALDAM 2023. Lecture Notes in Computer Science, vol 13947. Springer, Cham. https://doi.org/10.1007/978-3-031-25211-2_29
Download citation
DOI: https://doi.org/10.1007/978-3-031-25211-2_29
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-25210-5
Online ISBN: 978-3-031-25211-2
eBook Packages: Computer ScienceComputer Science (R0)