The k-regular induced subgraph problem

Abstract

We consider the problem of finding a maximum k-regular induced subgraph of a graph G. Theoretical results are established to compare upper bounds obtained from different techniques, including bounds from quadratic programming, Lagrangian relaxation and integer programming.

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.