8494 articles  [english version]

inria-00331747, version 1

Degree-Constrained Subgraph Problems: Hardness and Approximation Results

Omid Amini () 12, David Peleg 3, Stéphane Pérennes () 1, Ignasi Sau Valls () 1, Saket Saurabh 4

N° RR-6690 (2008)

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 three 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 three problems, are listed below. 1- The Maximum Degree-Bounded Connected Subgraph (MDBCS_d) problem takes as input a weight function w: E -> R+ and an integer d>1, and asks for a subset of edges E' such that the subgraph G'=(V,E') is connected, has maximum degree at most d, and the total edge-weight is maximized. We prove that MDBCS_d is not in APX for any d>1 (this was known only for d=2) and we provide a min{m/log n, nd/2log n}-approximation algorithm for unweighted graphs, and a min{n/2,m/d}-approximation algorithm for weighted graphs. 2- The Minimum Subgraph of Minimum Degree d (MSMD_d) problem consists in finding a smallest subgraph of G (in terms of number of vertices) with minimum degree at least d. For d=2 it corresponds to finding a shortest cycle of the graph. We prove that MSMD_d is not in APX for any d>2 and we provide an n/logn-approximation algorithm for the classes of graphs excluding a fixed graph as a minor, using dynamic programming techniques and a known structural result on graph minors. 3- The Dual Degree-Dense k-Subgraph (DDDkS) problem consists in finding a subgraph H of G such that |V(H)|

  • 1 :  MASCOTTE (INRIA Sophia Antipolis / Laboratoire I3S)
  • INRIA – Université Nice Sophia Antipolis [UNS] – CNRS : UMR7271
  • 2 :  Département de Mathématiques et Applications (DMA)
  • CNRS : UMR8553 – Ecole normale supérieure de Paris - ENS Paris
  • 3 :  Department of Computer Science and Applied Mathematics
  • Weizmann Institute of Science
  • 4 :  Department of Informatics
  • University of Bergen
  • Domaine : Mathématiques/Combinatoire
  • Référence interne : RR-6690
 
  • inria-00331747, version 1
  • oai:hal.inria.fr:inria-00331747
  • Contributeur : 
  • Soumis le : Vendredi 17 Octobre 2008, 15:05:02
  • Dernière modification le : Mardi 10 Juillet 2012, 15:35:22