Maximum square-free 2-matching

From Egres Open
Jump to: navigation, search

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


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.


  1. G. Cornuéjols, W.R. Pulleyblank, A matching problem with side conditions, Discrete Math. 29 (1980) 135-159, DOI link, ResearchGate link
  2. D. Hartvigsen, Extensions of matching theory, PhD thesis, Carnegie-Mellon University, 1984, pdf link
  3. Z. Király, Restricted t-matchings in bipartite graphs, EGRES Quick Proof
  4. 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
  5. Gy. Pap, Alternating paths revisited II: restricted b-matchings in bipartite graphs, EGRES Technical Report
  6. 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
  7. Y. Kobayashi, A simple algorithm for finding a maximum triangle-free 2-matching in subcubic graphs, DOI link, Technical Report
  8. D. Hartvigsen, The square-free 2-factor problem in bipartite graphs, DOI link
  9. 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
  10. Z. Király, [math]C_4[/math]-free 2-factors in bipartite graphs, EGRES Technical Report
  11. A. Frank, Restricted t-matchings in bipartite graphs, Discrete Appl. Math., 131(2):337-346, 2003, DOI link, EGRES Technical Report
  12. K. Bérczi, Y. Kobayashi, An algorithm for (n-3)-connectivity augmentation problem: Jump system approach, DOI link, Technical Report METR 2009-12
  13. K. Bérczi, L. A. Végh. Restricted b-matchings in degree-bounded graphs, DOI link, EGRES Technical Report
  14. W. H. Cunningham, Matching, matroids, and extensions, Math. Program., 91 (2002), pp. 515–542, DOI link, ResearchGate link
  15. Y. Kobayashi, J. Szabó, K. Takazawa, A proof to Cunningham's conjecture on restricted subgraphs and jump systems, DOI link, EGRES Technical Report