Finding a Maximum Restricted \({t}\)-Matching via Boolean Edge-CSP

Abstract. The problem of finding a maximum 2-matching without short cycles has received significant attention due to its relevance to the Hamiltonian cycle problem. This problem is generalized to finding a maximum [Formula: see text]-matching which excludes specified complete [Formula: see text]-partite subgraphs, where [Formula: see text] is a fixed positive integer. The polynomial solvability of this generalized problem remains an open question. In this paper, we present polynomial-time algorithms for the following two cases of this problem: in the first case the forbidden complete [Formula: see text]-partite subgraphs are edge-disjoint, and in the second case the maximum degree of the input graph is at most [Formula: see text]. Our result for the first case extends the previous work of Nam (1994), showing the polynomial solvability of the problem of finding a maximum 2-matching without cycles of length four, where the cycles of length four are vertex-disjoint. The second result expands upon the works of Bérczi and Végh (2010) and Kobayashi and Yin (2012), which focused on graphs with maximum degree at most [Formula: see text]. Our algorithms are obtained from exploiting the discrete structure of restricted [Formula: see text]-matchings and employing an algorithm for the Boolean edge-CSP.