Skip to main content
Springer Nature Link
Log in

Weighted Connected Matchings

  • Conference paper
  • First Online:
LATIN 2022: Theoretical Informatics (LATIN 2022)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 13568))

Included in the following conference series:

  • 819 Accesses

  • 3 Citations

Abstract

A matching M is a \(\mathscr {P}\)-matching if the subgraph induced by the endpoints of the edges of M satisfies property \(\mathscr {P}\). As examples, for appropriate choices of \(\mathscr {P}\), the problems Induced Matching, Uniquely Restricted Matching, Connected Matching and Disconnected Matching arise. For many of these problems, finding a maximum \(\mathscr {P}\)-matching is a knowingly \(\textsf{NP}\)-hard problem, with few exceptions, such as Connected Matching, which has the same time complexity as the usual Maximum Matching problem. The weighted variant of Maximum Matching has been studied for decades, with many applications, including the well-known Assignment problem. Motivated by this fact, in addition to some recent research in weighted versions of acyclic and induced matchings, we study the Maximum Weight Connected Matching. In this problem, we want to find a matching M such that the endpoints of its edges induce a connected subgraph and the sum of the edge weights of M is maximum. Unlike the unweighted Connected Matching problem, which is in \(\textsf{P}\) for general graphs, we show that Maximum Weight Connected Matching is \(\textsf{NP}\)-hard even for bounded diameter bipartite graphs, starlike graphs, planar bipartite graphs, and subcubic planar graphs, while solvable in linear time for trees and graphs having degree at most two. When we restrict edge weights to be non-negative only, we show that the problem turns out to be polynomially solvable for chordal graphs, while it remains \(\textsf{NP}\)-hard for most of the other cases. In addition, we consider parameterized complexity. On the positive side, we present a single exponential time algorithm when parameterized by treewidth. As for kernelization, we show that, even when restricted to binary weights, Weighted Connected Matching does not admit a polynomial kernel when parameterized by vertex cover number under standard complexity-theoretical hypotheses.

V.F. dos Santos—Partially supported by FAPEMIG and CNPq

J. L. Szwarcfiter—Partially supported by FAPERJ and CNPq.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
€34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
EUR 29.95
Price includes VAT (Germany)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
EUR 74.89
Price includes VAT (Germany)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
EUR 96.29
Price includes VAT (Germany)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

') var buybox = document.querySelector("[data-id=id_"+ timestamp +"]").parentNode var buyingOptions = buybox.querySelectorAll(".buying-option") ;[].slice.call(buyingOptions).forEach(initCollapsibles) var buyboxMaxSingleColumnWidth = 480 function initCollapsibles(subscription, index) { var toggle = subscription.querySelector(".buying-option-price") subscription.classList.remove("expanded") var form = subscription.querySelector(".buying-option-form") var priceInfo = subscription.querySelector(".price-info") var buyingOption = toggle.parentElement if (toggle && form && priceInfo) { toggle.setAttribute("role", "button") toggle.setAttribute("tabindex", "0") toggle.addEventListener("click", function (event) { var expandedBuyingOptions = buybox.querySelectorAll(".buying-option.expanded") var buyboxWidth = buybox.offsetWidth ;[].slice.call(expandedBuyingOptions).forEach(function(option) { if (buyboxWidth buyboxMaxSingleColumnWidth) { toggle.click() } else { if (index === 0) { toggle.click() } else { toggle.setAttribute("aria-expanded", "false") form.hidden = "hidden" priceInfo.hidden = "hidden" } } }) } initialStateOpen() if (window.buyboxInitialised) return window.buyboxInitialised = true initKeyControls() })()

Institutional subscriptions

Similar content being viewed by others

References

  1. Baste, J., Rautenbach, D.: Degenerate matchings and edge colorings. Discrete Appl. Math. 239, 38–44 (2018). https://doi.org/10.1016/j.dam.2018.01.002

    Article  MathSciNet  MATH  Google Scholar 

  2. Biasi, M.D.: Max-weight connected subgraph problem in planar graphs. Theor. Comput. Sci. Stack Exch. https://cstheory.stackexchange.com/q/21669

  3. Bodlaender, H.L., Cygan, M., Kratsch, S., Nederlof, J.: Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Inf. Comput. 243, 86–111 (2015). https://doi.org/10.1016/j.ic.2014.12.008, 40th International Colloquium on Automata, Languages and Programming (ICALP 2013)

  4. Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Cross-composition: a new technique for kernelization lower bounds. In: Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science (STACS), LIPIcs, vol. 9, pp. 165–176 (2011). https://doi.org/10.4230/LIPIcs.STACS.2011.165

  5. Bondy, J.A., Murty, U.S.R.: Graph Theory. Springer, London (2008). https://www.springer.com/gp/book/9781846289699

  6. Brandstädt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey. Society for Industrial and Applied Mathematics, Philadelphia (1999)

    Google Scholar 

  7. de C. M. Gomes, G., Masquio, B.P., Pinto, P.E.D., dos Santos, V.F., Szwarcfiter, J.L.: Disconnected matchings. CoRR abs/2112.09248 (2021). https://arxiv.org/abs/2112.09248

  8. Cameron, K.: Induced matchings. Discrete Appl. Math. 24(1), 97–102 (1989). https://doi.org/10.1016/0166-218X(92)90275-F

    Article  MathSciNet  MATH  Google Scholar 

  9. Cameron, K.: Connected matchings. In: Jünger, M., Reinelt, G., Rinaldi, G. (eds.) Combinatorial Optimization — Eureka, You Shrink! LNCS, vol. 2570, pp. 34–38. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-36478-1_5

    Chapter  Google Scholar 

  10. Cygan, M., et al.: Parameterized Algorithms. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-21275-3

    Book  MATH  Google Scholar 

  11. Duan, R., Pettie, S., Su, H.H.: Scaling algorithms for weighted matching in general graphs. ACM Trans. Algorithms 14(1) (2018). https://doi.org/10.1145/3155301

  12. Edmonds, J.: Maximum matching and a polyhedron with 0, 1-vertices. J. Res. Natl Bureau Stand. B 69, 125–130 (1965). https://doi.org/10.6028/jres.069B.013

    Article  MathSciNet  MATH  Google Scholar 

  13. Edmonds, J.: Paths, trees, and flowers. Can. J. Math. 17, 449–467 (1965). https://doi.org/10.4153/CJM-1965-045-4

    Article  MathSciNet  MATH  Google Scholar 

  14. Fürst, M., Rautenbach, D.: On some hard and some tractable cases of the maximum acyclic matching problem. Ann. Oper. Res. 279(1), 291–300 (2019). https://doi.org/10.1007/s10479-019-03311-1

  15. Garey, M.R., Johnson, D.S.: The rectilinear Steiner tree problem is NP-complete. SIAM J. Appl. Math. 32(4), 826–834 (1977). https://doi.org/10.1137/0132071

    Article  MathSciNet  MATH  Google Scholar 

  16. Garey, M.R., Johnson, D.S.: Computers and Intractability: a Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1979)

    Google Scholar 

  17. Goddard, W., Hedetniemi, S.M., Hedetniemi, S.T., Laskar, R.: Generalized subgraph-restricted matchings in graphs. Discrete Math. 293(1), 129–138 (2005). https://doi.org/10.1016/j.disc.2004.08.027

    Article  MathSciNet  MATH  Google Scholar 

  18. Golumbic, M.C., Hirst, T., Lewenstein, M.: Uniquely restricted matchings. Algorithmica 31(2), 139–154 (2001). https://doi.org/10.1007/s00453-001-0004-z

    Article  MathSciNet  MATH  Google Scholar 

  19. Gomes, G.C.M., Masquio, B.P., Pinto, P.E.D., dos Santos, V.F., Szwarcfiter, J.L.: Disconnected matchings. In: Chen, C.-Y., Hon, W.-K., Hung, L.-J., Lee, C.-W. (eds.) COCOON 2021. LNCS, vol. 13025, pp. 579–590. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-89543-3_48

    Chapter  Google Scholar 

  20. Karp, R.: Reducibility among combinatorial problems. In: Miller, R., Thatcher, J. (eds.) Complexity of Computer Computations, pp. 85–103. Plenum Press (1972). https://doi.org/10.1007/978-1-4684-2001-2_9

  21. Klemz, B., Rote, G.: Linear-time algorithms for maximum-weight induced matchings and minimum chain covers in convex bipartite graphs. Algorithmica 84(4), 1064–1080 (2022). https://doi.org/10.1007/s00453-021-00904-w

    Article  MathSciNet  MATH  Google Scholar 

  22. Kobler, D., Rotics, U.: 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). https://doi.org/10.1007/s00453-003-1035-4

    Article  MathSciNet  MATH  Google Scholar 

  23. Lichtenstein, D.: Planar formulae and their uses. SIAM J. Comput. 11(2), 329–343 (1982). https://doi.org/10.1137/0211025

    Article  MathSciNet  MATH  Google Scholar 

  24. Lozin, V.V.: On maximum induced matchings in bipartite graphs. Inf. Process. Lett. 81(1), 7–11 (2002). https://doi.org/10.1016/S0020-0190(01)00185-5

    Article  MathSciNet  MATH  Google Scholar 

  25. Masquio, B.P.: Emparelhamentos desconexos. Master’s thesis, Universidade do Estado do Rio de Janeiro (2019). http://www.bdtd.uerj.br/handle/1/7663

  26. Micali, S., Vazirani, V.V.: An \({O}(\sqrt{|V|}|{E}|)\) algorithm for finding maximum matching in general graphs. In: 21st Annual IEEE Symposium on Foundations of Computer Science, pp. 17–27, October 1980. https://doi.org/10.1109/SFCS.1980.12

  27. Moser, H., Sikdar, S.: The parameterized complexity of the induced matching problem. Discrete Appl. Math. 157(4), 715–727 (2009). https://doi.org/10.1016/j.dam.2008.07.011

    Article  MathSciNet  MATH  Google Scholar 

  28. Panda, B.S., Chaudhary, J.: Acyclic matching in some subclasses of graphs. In: Gąsieniec, 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

    Chapter  Google Scholar 

  29. Panda, B.S., Pandey, A., Chaudhary, J., Dane, P., Kashyap, M.: Maximum weight induced matching in some subclasses of bipartite graphs. J. Comb. Optim. 40(3), 713–732 (2020). https://doi.org/10.1007/s10878-020-00611-2

    Article  MathSciNet  MATH  Google Scholar 

  30. Robertson, N., Seymour, P.D.: Graph minors. II. algorithmic aspects of tree-width. J. Algorithms 7(3), 309–322 (1986). https://doi.org/10.1016/0196-6774(86)90023-4

Download references

Author information

Authors and Affiliations

  1. Universidade Federal de Minas Gerais (UFMG), Belo Horizonte, MG, Brazil

    Guilherme C. M. Gomes & Vinicius F. dos Santos

  2. Universidade do Estado do Rio de Janeiro (UERJ), Rio de Janeiro, RJ, Brazil

    Bruno P. Masquio, Paulo E. D. Pinto & Jayme L. Szwarcfiter

  3. Universidade Federal do Rio de Janeiro (UFRJ), Rio de Janeiro, RJ, Brazil

    Jayme L. Szwarcfiter

Authors
  1. Guilherme C. M. Gomes
    View author publications

    Search author on:PubMed Google Scholar

  2. Bruno P. Masquio
    View author publications

    Search author on:PubMed Google Scholar

  3. Paulo E. D. Pinto
    View author publications

    Search author on:PubMed Google Scholar

  4. Vinicius F. dos Santos
    View author publications

    Search author on:PubMed Google Scholar

  5. Jayme L. Szwarcfiter
    View author publications

    Search author on:PubMed Google Scholar

Corresponding author

Correspondence to Bruno P. Masquio .

Editor information

Editors and Affiliations

  1. Universidad Nacional Autónoma de México, Mexico City, Mexico

    Armando Castañeda

  2. Centro de investigación y de Estudios Avanzados, Mexico City, Mexico

    Francisco Rodríguez-Henríquez

Rights and permissions

Reprints and permissions

Copyright information

© 2022 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Gomes, G.C.M., Masquio, B.P., Pinto, P.E.D., Santos, V.F.d., Szwarcfiter, J.L. (2022). Weighted Connected Matchings. In: Castañeda, A., Rodríguez-Henríquez, F. (eds) LATIN 2022: Theoretical Informatics. LATIN 2022. Lecture Notes in Computer Science, vol 13568. Springer, Cham. https://doi.org/10.1007/978-3-031-20624-5_4

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-20624-5_4

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-20623-8

  • Online ISBN: 978-3-031-20624-5

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics