A note on the complexity of finding regular subgraphs (Q1059641)

This is an interesting investigation on the algorithmic difficulty of detecting regular subgraphs in a given graph. The author proves a general theorem which states that, for a given graph G and an integer \(r\geq 3\), the problem of deciding the existence of an r-regular subgraph of G is NP-complete. NP-completeness is proved by polynomial reduction of the known NP-complete problem ''exact cover by 3-sets'' to the new problem. Stronger results are then presented; these show that the r-regular subgraph problem remains NP-complete even when G is a bipartite or planar graph with given characteristics.