Abstract:

The maximum degree-bounded connected subgraph (MDBCS_d for short) problem
takes as input an undirected graph G=3D(V,E) and an integer d >1, and 
asks for a subset E' of E, such that the subgraph H induced by E' is connected, 
has maximum degree at most d, and |E'| is maximized. In the weighted version,
there is also a weight funcion on E, and the objective function to be
maximized is the sum of the weights of the edges in E'.

This problem is one of the classical NP-hard problems listed by Garey and
Johnson in their book of 1979, but there were no results in the literature
except for the case d=3D2, a.k.a. the LONGEST PATH problem. 
(Interestingly, if H is not required to be connected, then the problem is 
in P for any d.)  

In this talk we will first describe a simple approximation algorithm that,
for any d >1, finds a solution of MDBCS_d in general weighted graphs within
a factor min{n,m/d}of the optimal solution, with n=3D|V| and m=3D|E|. In 
the second part of the talk we will sketch the main ideas that allow us to 
prove that MDBCS_d is not in APX for any d >1. Roughly, the proof consists in
ruling out the existence of a PTAS by reduction from a variant of the
Traveling Salesman Problem, and then using appropriately the error
amplification technique. 

This is joint work with Omid Amini, David Peleg, Stephane Perennes, 
and Saket Saurabh.