A simple algorithm for finding a maximum triangle-free 22-matching in subcubic graphs

In this paper, we consider the problem of finding a maximum weight 22-matching containing no cycle of a length of at most three in a weighted simple graph, which we call the weighted triangle-free 22-matching problem. Although the polynomial solvability of this problem is still open in general graphs, a polynomial-time algorithm is given by Hartvigsen and Li for the problem in subcubic graphs, i.e., graphs with a maximum degree of at most three. Our contribution is to provide another polynomial-time algorithm for the weighted triangle-free 22-matching problem in subcubic graphs. Our algorithm consists of two basic algorithms: a steepest ascent algorithm and a classical maximum weight22-matching algorithm, and is justified by fundamental results from the theory of discrete convex functions on jump systems.