Abstract
A 2-matching in an undirected graph G = (VG, EG) is a function x: EG →{0,1,2} such that for each node v ∈ VG the sum of values x(e) on all edges e incident to v does not exceed 2. The size of x is the sum ∑ e x(e). If {e ∈ EGx(e) ≠ 0} contains no triangles then x is called triangle-free.
Cornuéjols and Pulleyblank devised a combinatorial O(mn)-algorithm that finds a triangle free 2-matching of maximum size (hereinafter n : = |VG|, m : = |EG|) and also established a min-max theorem.
We claim that this approach is, in fact, superfluous by demonstrating how their results may be obtained directly from the Edmonds–Gallai decomposition. Applying the algorithm of Micali and Vazirani we are able to find a maximum triangle-free 2-matching in \(O(m\sqrt{n})\)-time. Also we give a short self-contained algorithmic proof of the min-max theorem.
Next, we consider the case of regular graphs. It is well-known that every regular graph admits a perfect 2-matching. One can easily strengthen this result and prove that every d-regular graph (for d ≥ 3) contains a perfect triangle-free 2-matching. We give the following algorithms for finding a perfect triangle-free 2-matching in a d-regular graph: an O(n)-algorithm for d = 3, an O(m + n 3/2)-algorithm for d = 2k (k ≥ 2), and an O(n 2)-algorithm for d = 2k + 1 (k ≥ 2).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Cole, R., Ost, K., Schirra, S.: Edge-coloring bipartite multigraphs in O(E logD) time. Combinatorica 21, 5–12 (2001)
Cornuéjols, G., Pulleyblank, W.R.: Perfect triangle-free 2-matchings. Mathematical Programming Studies 13, 1–7 (1980)
Cornuéjols, G., Pulleyblank, W.R.: Critical graphs, matchings and tours or a hierarchy of relaxations for the travelling salesman problem. Combinatorica 3(1), 35–52 (1983)
Hopcroft, J.E., Karp, R.M.: An n 5/2 algorithm for maximum matchings in bipartite graphs. SIAM Journal on Computing 2(4), 225–231 (1973)
Lovász, L., Plummer, M.D.: Matching Theory. Akadémiai Kiadó, North Holland (1986)
Micali, S., Vazirani, V.: An \(O(\sqrt{|V|}.|E|)\) algorithm for finding maximum matching in general graphs. In: Proc. 21st IEEE Symp. Foundations of Computer Science, pp. 248–255 (1980)
Schrijver, A.: Combinatorial Optimization. Springer, Berlin (2003)
Voorhoeve, M.: A lower bound for the permanents of certain (0, 1)-matrices. Nederl. Akad. Wetensch. Indag. Math. 41(1), 83–86 (1979)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Babenko, M., Gusakov, A., Razenshteyn, I. (2010). Triangle-Free 2-Matchings Revisited. In: Thai, M.T., Sahni, S. (eds) Computing and Combinatorics. COCOON 2010. Lecture Notes in Computer Science, vol 6196. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-14031-0_15
Download citation
DOI: https://doi.org/10.1007/978-3-642-14031-0_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-14030-3
Online ISBN: 978-3-642-14031-0
eBook Packages: Computer ScienceComputer Science (R0)