Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Faster Algorithm for Finding Maximum 1-Restricted Simple 2-Matchings

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

We revisit the problem of finding a 1-restricted simple 2-matching of maximum cardinality. Recall that, given an undirected graph \({\varvec{G = (V, E)}}\), a simple 2-matching is a subset \({\varvec{M}} \subseteq {\varvec{E}}\) of edges such that each node in \({\varvec{V}}\) is incident to at most two edges in \({\varvec{M}}\). Clearly, each such \({\varvec{M}}\) decomposes into a node-disjoint collection of paths and circuits. \({\varvec{M}}\) is called 1-restricted if it contains no isolated edges (i.e. paths of length one). A combinatorial polynomial algorithm for finding such \({\varvec{M}}\) of maximum cardinality and also a min-max relation were devised by Hartvigsen. It was shown that finding such \({\varvec{M}}\) amounts to computing a (not necessarily 1-restricted) simple 2-matching \({\varvec{M}}_{\varvec{0}}\) of maximum cardinality and subsequently altering it into \({\varvec{M}}\) of the same cardinality so as to minimize the number of isolated edges. While the first phase (which computes \({\varvec{M}}_{\varvec{0}}\)) runs in \({\varvec{O}}\left( {\varvec{E}} \sqrt{V}\right) \) time, the second one (which turns \({\varvec{M}}_{\varvec{0}}\) into \({\varvec{M}}\)) requires \({\varvec{O(VE)}}\) time. In this paper we apply the general blocking augmentation approach (initially introduced, e.g., for bipartite matchings by Hopcroft and Karp, and also by Dinic) and present a novel algorithm that reduces the time needed for the second phase to \({\varvec{O}}\left( \textbf{E} \sqrt{V}\right) \) thus completely closing the gap between 1-restricted and unrestricted cases.

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

Access this article

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

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9

Similar content being viewed by others

References

  1. Hartvigsen, D.: Maximum cardinality 1-restricted simple 2-matchings. Electron. J. Comb. 14(1), R73 (2007)

    Article  MathSciNet  Google Scholar 

  2. Goldberg, A.V., Karzanov, A.V.: Maximum skew-symmetric flows and matchings. Math. Progr. 100(3), 537–568 (2004)

    Article  MathSciNet  Google Scholar 

  3. Hopcroft, J.E., Karp, R.M.: An \(n^{5/2}\) algorithm for maximum matchings in bipartite graphs. SIAM J. Comput. 2(4), 225–231 (1973)

    Article  MathSciNet  Google Scholar 

  4. Kaneko, A.: A necessary and sufficient condition for the existence of a path factor every component of which is a path of length at least two. J. Comb. Theory Ser. B 88(2), 195–218 (2003). https://doi.org/10.1016/S0095-8956(03)00027-3

    Article  MathSciNet  Google Scholar 

  5. Kano, M., Katona, G.Y., Király, Z.: Packing paths of length at least two. Discret. Math. 283(1–3), 129–135 (2004). https://doi.org/10.1016/j.disc.2004.01.016

    Article  MathSciNet  Google Scholar 

  6. Hartvigsen, D., Hell, P., Szabó, J.: The k-piece packing problem. J. Graph Theory 52(4), 267–293 (2006). https://doi.org/10.1002/jgt.20161

    Article  MathSciNet  Google Scholar 

  7. Artamonov, S., Babenko, M.A.: Faster algorithm for finding maximum 1-restricted simple 2-matchings. In: Bazgan, C., Fernau, H. (eds.) Combinatorial Algorithms - 33rd International Workshop, IWOCA 2022, Trier, Germany, June 7–9, 2022, Proceedings. Lecture Notes in Computer Science, vol. 13270, pp. 86–100. Springer, NY (2022)

    Google Scholar 

  8. Lovász, L., Plummer, M.D.: Matching Theory. North-Holland, NY (1986)

    Google Scholar 

Download references

Funding

The authors did not receive support from any organization for the submitted work.

Author information

Authors and Affiliations

  1. Moscow State University, Leninskie Gory, 1, Moscow, Russia, 119991

    Stepan Artamonov

  2. National Research University Higher School of Economics, Myasnitskaya Ulitsa, 20, Moscow, Russia, 101000

    Maxim Babenko

Authors
  1. Stepan Artamonov
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Maxim Babenko
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Maxim Babenko.

Ethics declarations

Conflict of interest

The authors have no relevant financial or non-financial interests to disclose.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Artamonov, S., Babenko, M. Faster Algorithm for Finding Maximum 1-Restricted Simple 2-Matchings. Algorithmica 86, 717–734 (2024). https://doi.org/10.1007/s00453-023-01148-6

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-023-01148-6

Keywords

Search

Navigation