Degree-Constrained Subgraph Problems: Hardness and Approximation Results

摘要

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 |V| = n and |E| = m. Our results, together with the definition of the two problems, are listed below. (1) The MAXIMUM DEGREE-BOUNDED CONNECTED SUBGRAPH problem (MDBCS_d) takes as input a weight function ω : E → R~+ and an integer d ≥ 2, and asks for a subset E' {is contained in} E such that the subgraph G' = (V, E') is connected, has maximum degree at most d, and ∑_(e∈E') ω(e) is maximized. This problem is one of the classical NP-hard problems listed by Garey and Johnson in [Computers and Intractability, W.H. Freeman, 1979], but there were no results in the literature except for d = 2. We prove that MDBCS_d is not in APX for any d ≥ 2 (this was known only for d = 2) and we provide a (min{m/log n, nd/(2 log n)})-approximation algorithm for unweighted graphs, and a (min{n/2, m/d})-approximation algorithm for weighted graphs. We also prove that when G has a low-degree spanning tree, in terms of d, MDBCS_d can be approximated within a small constant factor in unweighted graphs. (2) The MINIMUM SUBGRAPH OF MINIMUM DEGREE_( ≥ d) (MSMD_d) problem requires finding a smallest subgraph of G (in terms of number of vertices) with minimum degree at least d. We prove that MSMD_d 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.