MASCOTTE no longer exists => visit the new project-team
Seminaire MASCOTTEMaximum Degree-Bounded Connected Subgraph: Hardness and Approximation
par Ignasi Sau Valls
| Date : | 29/04/08 | | Location : | Salle du Conseil |
The maximum degree-bounded connected subgraph (MDBCS_d for short) problem takes as input an undirected graph G=(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=2, 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=|V| and m=|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, Stéphane Perénnes, and Saket Saurabh.
Page des séminaires
| 
