Finding a maximum 2-matching excluding prescribed cycles in bipartite graphs

We introduce a new framework for restricted 2-matchings close to Hamilton cycles. For an undirected graph (V,E) and a family U of vertex subsets, a 2-matching F is called U-feasible if |F[U]|≤|U|−1 for each U∈U, where F[U] is the set of edges in F induced by U. If F is a 2-factor, this property makes F satisfy the subtour elimination constraint for U∈U. Our framework can describe C≤k-free 2-matchings, i.e., 2-matchings without cycles of at most k edges, and 2-factors covering prescribed edge cuts, both of which are intensively studied as relaxations of Hamilton cycles. While the problem of finding a maximum U-feasible 2-matching is NP-hard, we prove that the problem is tractable when the graph is bipartite and each U∈U induces a Hamilton-laceable graph. This case generalizes the C≤4-free 2-matching problem in bipartite graphs. We establish a min-max theorem, a combinatorial polynomial-time algorithm, and decomposition theorems by extending the theory of C≤4-free 2-matchings. Our result provides the first polynomially solvable case for the maximum C≤k-free 2-matching problem for k≥5. For instance, in bipartite graphs in which every cycle of length six has at least two chords, our algorithm solves the maximum C≤6-free 2-matching problem in O(n2m) time, where n and m are the numbers of vertices and edges, respectively.