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.


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

  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
Retrieved from "http://lemon.cs.elte.hu/egres/internals/index.php5?title=Maximum_square-free_2-matching&oldid=2070"