The k-regular induced subgraph problem

This general problem includes well-known subproblems as particular cases of k. In this paper we focus on two particular cases. The case k=1 which is the maximal cardinality strong-matching and the case of finding the maximal cardinality family of induced cycles (k=2). For each one of the two cases, combinatorial algorithms are presented to solve the problem when graphs have particular structures and polyhedral descriptions of the convex hull of the corresponding feasible set are given. Computational tests are reported to compare the different upper bounds with the optimal values for different values of k, and to test the effectiveness of the inequalities introduced.