Maximum Induced Matching Algorithms via Vertex Ordering Characterizations

Authors Michel Habib, Lalla Mouatadid



PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2017.43.pdf
  • Filesize: 0.54 MB
  • 12 pages

Document Identifiers

Author Details

Michel Habib
Lalla Mouatadid

Cite AsGet BibTex

Michel Habib and Lalla Mouatadid. Maximum Induced Matching Algorithms via Vertex Ordering Characterizations. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 43:1-43:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.ISAAC.2017.43

Abstract

We study the maximum induced matching problem on a graph G. Induced matchings correspond to independent sets in L^2(G), the square of the line graph of G. The problem is NP-complete on bipartite graphs. In this work, we show that for a number of graph families with forbidden vertex orderings, almost all forbidden patterns on three vertices are preserved when taking the square of the line graph. These orderings can be computed in linear time in the size of the input graph. In particular, given a graph class \mathcal{G} characterized by a vertex ordering, and a graph G=(V,E) \in \mathcal{G} with a corresponding vertex ordering \sigma of V, one can produce (in linear time in the size of G) an ordering on the vertices of L^2(G), that shows that L^2(G) \in \mathcal{G} - for a number of graph classes \mathcal{G} - without computing the line graph or the square of the line graph of G. These results generalize and unify previous ones on showing closure under L^2(\cdot) for various graph families. Furthermore, these orderings on L^2(G) can be exploited algorithmically to compute a maximum induced matching on G faster. We illustrate this latter fact in the second half of the paper where we focus on cocomparability graphs, a large graph class that includes interval, permutation, trapezoid graphs, and co-graphs, and we present the first \mathcal{O}(mn) time algorithm to compute a maximum weighted induced matching on cocomparability graphs; an improvement from the best known \mathcal{O}(n^4) time algorithm for the unweighted case.
Keywords
  • Maximum induced matching
  • Independent set
  • Vertex ordering charac- terization
  • Graph classes
  • Fast algorithms
  • Cocomparability graphs

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Hari Balakrishnan, Christopher L. Barrett, V. S. Anil Kumar, Madhav V. Marathe, and Shripad Thite. The distance-2 matching problem and its relationship to the mac-layer capacity of ad hoc wireless networks. IEEE Journal on Selected Areas in Communications, 22(6):1069-1079, 2004. Google Scholar
  2. Vincenzo Bonifaci, Peter Korteweg, Alberto Marchetti-Spaccamela, and Leen Stougie. Minimizing flow time in the wireless gathering problem. ACM Trans. Algorithms, 7(3):33:1-33:20, 2011. Google Scholar
  3. Andreas Brandstädt and Chính T. Hoàng. Maximum induced matchings for chordal graphs in linear time. Algorithmica, 52(4):440-447, 2008. Google Scholar
  4. Andreas Brandstädt, Van Bang Le, and Jeremy P. Spinrad. Graph Classes: A Survey. Society for Industrial and Applied Mathematics, 1999. Google Scholar
  5. Kathie Cameron. Induced matchings. Discrete Applied Mathematics, 24(1-3):97-102, 1989. Google Scholar
  6. Kathie Cameron. Induced matchings in intersection graphs. Discrete Mathematics, 278(1-3):1-9, 2004. Google Scholar
  7. Kathie Cameron, R. Sritharan, and Yingwen Tang. Finding a maximum induced matching in weakly chordal graphs. Discrete Mathematics, 266(1-3):133-142, 2003. Google Scholar
  8. Jou-Ming Chang. Induced matchings in asteroidal triple-free graphs. Discrete Applied Mathematics, 132(1-3):67-78, 2003. Google Scholar
  9. Pierre Charbit, Michel Habib, Lalla Mouatadid, and Reza Naserasr. Towards A unified view of linear structure on graph classes. CoRR, abs/1702.02133, 2017. Google Scholar
  10. Derek G. Corneil, Barnaby Dalton, and Michel Habib. Ldfs-based certifying algorithm for the minimum path cover problem on cocomparability graphs. SIAM J. Comput., 42(3):792-807, 2013. Google Scholar
  11. Derek G. Corneil, Jérémie Dusart, Michel Habib, and Ekkehard Köhler. On the power of graph searching for cocomparability graphs. SIAM J. Discrete Math., 30(1):569-591, 2016. Google Scholar
  12. Peter Damaschke. Forbidden Ordered Subgraphs. Topics in Combinatorics and Graph Theory: Essays in Honour of Gerhard Ringel. Physica-Verlag HD, 1990. Google Scholar
  13. William Duckworth, David Manlove, and Michele Zito. On the approximability of the maximum induced matching problem. J. Discrete Algorithms, 3(1):79-91, 2005. Google Scholar
  14. Shimon Even, Oded Goldreich, Shlomo Moran, and Po Tong. On the np-completeness of certain network testing problems. Networks, 14(1):1-24, 1984. Google Scholar
  15. Martin C. Golumbic. Algorithmic Graph Theory and Perfect Graphs (Annals of Discrete Mathematics), volume 57. North-Holland Publishing Co., 2004. Google Scholar
  16. Martin Charles Golumbic and Renu C. Laskar. Irredundancy in circular arc graphs. Discrete Applied Mathematics, 44(1-3):79-89, 1993. Google Scholar
  17. Martin Charles Golumbic and Moshe Lewenstein. New results on induced matchings. Discrete Applied Mathematics, 101(1-3):157-165, 2000. Google Scholar
  18. Martin Charles Golumbic, Doron Rotem, and Jorge Urrutia. Comparability graphs and intersection graphs. Discrete Mathematics, 43(1):37-46, 1983. Google Scholar
  19. Michel Habib and Lalla Mouatadid. Maximum induced matching algorithms via vertex ordering characterizations. CoRR, abs/1707.01245, 2017. Google Scholar
  20. Pavol Hell, Bojan Mohar, and Arash Rafiey. Ordering without forbidden patterns. In Algorithms - ESA 2014 - 22th Annual European Symposium, Wroclaw, Poland, September 8-10, 2014. Proceedings, pages 554-565, 2014. Google Scholar
  21. Changhee Joo, Gaurav Sharma, Ness B. Shroff, and Ravi R. Mazumdar. On the complexity of scheduling in wireless networks. EURASIP J. Wireless Comm. and Networking, 2010, 2010. Google Scholar
  22. Daniel Kobler and Udi Rotics. Finding maximum induced matchings in subclasses of claw-free and p5-free graphs, and in graphs with matching and induced matching of equal maximum size. Algorithmica, 37(4):327-346, 2003. Google Scholar
  23. Ekkehard Köhler and Lalla Mouatadid. Linear time lexdfs on cocomparability graphs. In Algorithm Theory - SWAT 2014 - 14th Scandinavian Symposium and Workshops, Copenhagen, Denmark, July 2-4, 2014. Proceedings, pages 319-330, 2014. Google Scholar
  24. Ekkehard Köhler and Lalla Mouatadid. A linear time algorithm to compute a maximum weighted independent set on cocomparability graphs. Inf. Process. Lett., 116(6):391-395, 2016. Google Scholar
  25. Dieter Kratsch and Lorna Stewart. Domination on cocomparability graphs. SIAM J. Discrete Math., 6(3):400-417, 1993. Google Scholar
  26. Ravi Kumar, Uma Mahadevan, and D. Sivakumar. A graph-theoretic approach to extract storylines from search results. In Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Seattle, Washington, USA, August 22-25, 2004, pages 216-225, 2004. Google Scholar
  27. Vadim V. Lozin. On maximum induced matchings in bipartite graphs. Inf. Process. Lett., 81(1):7-11, 2002. Google Scholar
  28. Ross M. McConnell and Jeremy P. Spinrad. Modular decomposition and transitive orientation. Discrete Mathematics, 201(1-3):189-241, 1999. Google Scholar
  29. George B. Mertzios and Derek G. Corneil. A simple polynomial algorithm for the longest path problem on cocomparability graphs. SIAM J. Discrete Math., 26(3):940-963, 2012. Google Scholar
  30. George B. Mertzios, André Nichterlein, and Rolf Niedermeier. Linear-time algorithm for maximum-cardinality matching on cocomparability graphs. CoRR, abs/1703.05598, 2017. Google Scholar
  31. Hannes Moser and Somnath Sikdar. The parameterized complexity of the induced matching problem in planar graphs. In Frontiers in Algorithmics, First Annual International Workshop, FAW 2007, Lanzhou, China, August 1-3, 2007, Proceedings, pages 325-336, 2007. Google Scholar
  32. Donald J. Rose, Robert Endre Tarjan, and George S. Lueker. Algorithmic aspects of vertex elimination on graphs. SIAM J. Comput., 5(2):266-283, 1976. Google Scholar
  33. Larry J. Stockmeyer and Vijay V. Vazirani. Np-completeness of some generalizations of the maximum matching problem. Inf. Process. Lett., 15(1):14-19, 1982. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail