On approximating the dd-girth of a graph

For a finite, simple, undirected graph GG and an integer d≥1d≥1, a mindeg-  ddsubgraph   is a subgraph of GG of minimum degree at least dd. The dd-girth   of GG, denoted by gd(G)gd(G), is the minimum size of a mindeg-dd subgraph of GG. It is a natural generalization of the usual girth, which coincides with the 2-girth. The notion of dd-girth was proposed by Erdős et al. (1988, 1990)  [14] and [15] and Bollobás and Brightwell (1989)  [8] over 25 years ago, and studied from a purely combinatorial point of view. Since then, no new insights have appeared in the literature. Recently, first algorithmic studies of the problem have been carried out by Amini et al. (2012a,b)  [2] and [4]. The current article further explores the complexity of finding a small mindeg-dd subgraph of a given graph (that is, approximating its dd-girth), by providing new hardness results and the first approximation algorithms in general graphs, as well as analyzing the case where GG is planar.