On the approximability of some degree-constrained subgraph problems

Abstract: In this article we provide hardness results and approximation algorithms for the following three natural degree-constrained subgraph problems, which take as input an undirected graph . Let be a fixed integer. The () problem takes as additional input a weight function , and asks for a subset such that the subgraph induced by is connected, has maximum degree at most , and is maximized. The Minimum Subgraph of Minimum Degree () problem involves finding a smallest subgraph of with minimum degree at least . Finally, the Dual Degree-dense -Subgraph () problem consists in finding a subgraph of such that and the minimum degree in is maximized. [Copyright &y& Elsevier]