Résumé
A general instance of a DEGREE-CONSTRAINED SUBGRAPH problem consists of an edge-weighted or vertex-weighted graph G and the objective is to find an optimal weighted subgraph, subject to certain degree constraints on the vertices of the subgraph. This paper considers two natural DEGREE-CONSTRAINED SUBGRAPH problems and studies their behavior in terms of approximation algorithms. These problems take as input an undirected graph G = (V, E), with vertical bar V vertical bar = n and vertical bar E vertical bar = m. Our results, together with the definition of the two problems, are listed below.
The MAXIMUM DEGREE-BOUNDED CONNECTED SUBGRAPH problem (MDBCSd) takes as input a weight function w : E -> R+ and an integer d >= 2, and asks for a subset E' subset of E such that the subgraph G' = (V,E') is connected, has maximum degree at most d, and Sigma(e is an element of E') w(e) is maximized. This problem is one of the classical NP-hard problems listed by Garey and Johnson in [Computers and Intractability, W.H. F -eeman, 1979], but there were no results in the literature except for d = 2. We prove that MDBCSd is not in Apx for any d >= 2 (this was known only for d = 2) and we provide a (minjm/ log 7t, nd/(2 logn)J)-approximation algorithm for unweighted graphs, and a (mirifn/2, Trt/dj)-approxiniation algorithin for weighted graphs. We also prove that when G has a lowdegree spanning tree, in terms of d, MDBCSd can be approximated within a small constant factor in unweighted graphs.
The MINIMUM SUBGRAPH OF MINIMUM DEGREE(>= d) (MSMDd) problem requires finding a smallest subgraph of G (in terms of number of vertices) with minimum degree at least d. We prove that MSMDd is not in APX for any d >= 3 and we provide an O(n/ log n)-approximation algorithm for the class of graphs excluding a fixed graph as a minor, using dynamic programming techniques and a known structural result on graph minors.