# Maximum square-free 2-matching

Given an undirected graph *G=(V,E)*, find a maximum cardinality 2-matching containing no cycles of length 4 in polynomial time.

## Remarks

A **2-matching** is a subgraph of maximum degree 2. A natural relaxation of the Hamiltonian cycle problem is to find a maximum 2-matching containing no cycles of length at most *k*, also called the *maximum [math]C_{\leq k}[/math]-free 2-matching problem*. For [math]k\geq 5[/math], this problem is NP-complete ^{[1]}. Hartvigsen ^{[2]} proposed a solution for *k=3*. Hence the remaining cases are the square-free 2-matching and the triangle- and square-free 2-matching problems.

For the weighted version, Király ^{[3]} showed that the problem is NP-complete for *k = 4* even in bipartite graphs with 0-1 weights on the edges. A polynomially solvable special case in bipartite graphs ^{[4]}^{[5]} is when the weight function is *vertex induced* on every square (a weight function is vertex induced if for any square with edges [math]e_1,e_2,e_3,e_4[/math] -in order around the square- the sum of the weights of [math]e_1[/math] and [math]e_3[/math] is the same as for [math]e_2[/math] and [math]e_4[/math]). For k=3, Hartvigsen and Li ^{[6]}, and Kobayashi ^{[7]} gave polynomial-time algorithm when the graph is subcubic, that is, when all nodes have degree at most three.

Considering bipartite graphs, the problem of *maximum square-free 2-matchings* was solved by Hartvigsen ^{[8]}^{[9]} and Király ^{[10]}. Frank ^{[11]} gave a generalization to [math]K_{t,t}[/math]-free t-matchings by observing that this is a special case of the Frank-Jordán theorem.

For general graphs, finding a maximum square-free 2-matching is still open. The special case of subcubic graphs was solved by Bérczi and Kobayashi ^{[12]}, and this was slightly generalized to restricted b-matchings by Bérczi and Végh ^{[13]}.

The degree sequences of the [math]C_{\leq k}[/math]-free 2-matchings form a jump system for [math]k \leq 3[/math], and do not always form a jump system for [math]k \geq 5[/math], in alignment with the complexity of the maximization problem. Cunningham ^{[14]} conjectured that the maximum [math]C_{\leq 4}[/math]-free 2-matching problem is polynomial time solvable, and that the degree sequences of [math]C_{\leq 4}[/math]-free 2-matchings form a jump system. The latter part of this conjecture was confirmed by Kobayashi, Szabó and Takazawa ^{[15]}, yielding a slight indication that the maximization problem may also be solvable in polynomial time. They also proved that the degree sequences of square-free 2-matchings form a jump system, and that the weighted [math]C_{\leq 4}[/math]-free 2-matchings in a bipartite graph induce an M-concave function on the jump system if and only if the weight function is vertex-induced on every square. This result is also consistent with the polynomial solvability of the weighted [math]C_{\leq 4}[/math]-free 2-matching problem in bipartite graphs.

## Related conjectures

The problem is equivalent to Undirected node-connectivity augmentation in the complement of the graph for connectivity requirement *n-3*.

## References

- ↑ G. Cornuéjols, W.R. Pulleyblank,
*A matching problem with side conditions*, Discrete Math. 29 (1980) 135-159, DOI link, ResearchGate link - ↑ D. Hartvigsen,
*Extensions of matching theory*, PhD thesis, Carnegie-Mellon University, 1984, pdf link - ↑ Z. Király,
*Restricted t-matchings in bipartite graphs*, EGRES Quick Proof - ↑ M. Makai,
*On maximum cost [math]K_{t;t}[/math]-free t-matchings of bipartite graphs*, SIAM J. Discret. Math., 21(2):349-360, 2007, DOI link - ↑ Gy. Pap,
*Alternating paths revisited II: restricted b-matchings in bipartite graphs*, EGRES Technical Report - ↑ D. Hartvigsen, Y. Li,
*Triangle-free simple 2-matchings in subcubic graphs*(extended abstract)*, In Lecture Notes in Computer Science, pages 43-52, London, UK, 2007. Springer-Verlag, DOI link* - ↑ Y. Kobayashi,
*A simple algorithm for finding a maximum triangle-free 2-matching in subcubic graphs*, DOI link, Technical Report - ↑ D. Hartvigsen,
*The square-free 2-factor problem in bipartite graphs*, DOI link - ↑ D. Hartvigsen,
*Finding maximum square-free 2-matchings in bipartite graphs*, J. Comb. Theory Ser. B, 96(5):693-705, 2006, DOI link, ResearchGate link - ↑ Z. Király,
*[math]C_4[/math]-free 2-factors in bipartite graphs*, EGRES Technical Report - ↑ A. Frank,
*Restricted t-matchings in bipartite graphs*, Discrete Appl. Math., 131(2):337-346, 2003, DOI link, EGRES Technical Report - ↑ K. Bérczi, Y. Kobayashi,
*An algorithm for (n-3)-connectivity augmentation problem: Jump system approach*, DOI link, Technical Report METR 2009-12 - ↑ K. Bérczi, L. A. Végh.
*Restricted b-matchings in degree-bounded graphs*, DOI link, EGRES Technical Report - ↑ W. H. Cunningham,
*Matching, matroids, and extensions*, Math. Program., 91 (2002), pp. 515–542, DOI link, ResearchGate link - ↑ Y. Kobayashi, J. Szabó, K. Takazawa,
*A proof to Cunningham's conjecture on restricted subgraphs and jump systems*, DOI link, EGRES Technical Report