On the approximability of some degree-constrained subgraph problems

被引:18
作者
Amini, Omid [2 ]
Peleg, David [3 ]
Perennes, Stephane [4 ]
Sau, Ignasi [1 ]
Saurabh, Saket [5 ]
机构
[1] CNRS, LIRMM, Montpellier, France
[2] Ecole Normale Super, CNRS, DMA, Paris, France
[3] Weizmann Inst Sci, IL-76100 Rehovot, Israel
[4] INRIA CNRS UNS, Mascotte project, Sophia Antipolis, France
[5] Inst Math Sci, Chennai 600113, Tamil Nadu, India
关键词
Degree-constrained subgraph; Approximation algorithms; Hardness of approximation; DENSE K-SUBGRAPH; APPROXIMATION; OPTIMIZATION; COMPLEXITY; HARDNESS; PATH;
D O I
10.1016/j.dam.2012.03.025
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
In this article we provide hardness results and approximation algorithms for the following three natural degree-constrained subgraph problems, which take as input an undirected graph G = (V, E). Let d >= 2 be a fixed integer. The MAXIMUM d - DEGREE-BOUNDED CONNECTED SUBGRAPH (MDBCSd) problem takes as additional input a weight function omega : E -> R+, and asks for a subset E' subset of E such that the subgraph induced by E' is connected, has maximum degree at most d, and Sigma(e is an element of E') omega(e) is maximized. The MINIMUM SUBGRAPH OF MINIMUM DEGREE >= d (MSMDd) problem involves finding a smallest subgraph of G with minimum degree at least d. Finally, the DUAL DEGREE-DENSE k-SUBGRAPH (DDDkS) problem consists in finding a subgraph H of G such that vertical bar V(H)vertical bar <= k and the minimum degree in H is maximized. (C) 2012 Elsevier B.V. All rights reserved.
引用
收藏
页码:1661 / 1679
页数:19
相关论文
共 50 条
  • [31] On the approximability of covering points by lines and related problems
    Dumitrescu, Adrian
    Jiang, Minghui
    COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2015, 48 (09): : 703 - 717
  • [32] Approximability of Unsplittable Shortest Path Routing Problems
    Bley, Andreas
    NETWORKS, 2009, 54 (01) : 23 - 46
  • [33] On the approximability of minmax (regret) network optimization problems
    Kasperski, Adam
    Zieliniski, Pawel
    INFORMATION PROCESSING LETTERS, 2009, 109 (05) : 262 - 266
  • [34] Approximability of scheduling problems with resource consuming jobs
    Gyoergyi, Peter
    Kis, Tamas
    ANNALS OF OPERATIONS RESEARCH, 2015, 235 (01) : 319 - 336
  • [35] Approximating the maximum clique minor and some subgraph homeomorphism problems
    Alon, Noga
    Lingas, Andrzej
    Wahlen, Martin
    THEORETICAL COMPUTER SCIENCE, 2007, 374 (1-3) : 149 - 158
  • [36] On the approximability of the maximum interval constrained coloring problem
    Canzar, Stefan
    Elbassioni, Khaled
    Elmasry, Amr
    Raman, Rajiv
    DISCRETE OPTIMIZATION, 2018, 27 : 57 - 72
  • [37] On the Ordered List Subgraph Embedding Problems
    Hassan, Olawale
    Kanj, Iyad
    Lokshtanov, Daniel
    Perkovic, Ljubomir
    ALGORITHMICA, 2016, 74 (03) : 992 - 1018
  • [38] On the complexity and approximability of budget-constrained minimum-cost flows
    Holzhauser, Michael
    Krunike, Sven O.
    Thielen, Clemens
    INFORMATION PROCESSING LETTERS, 2017, 126 : 24 - 29
  • [39] On the approximability of Dense Steiner Problems
    Hauptmann, Mathias
    JOURNAL OF DISCRETE ALGORITHMS, 2013, 21 : 41 - 51
  • [40] Improved approximability and non-approximability results for graph diameter decreasing problems
    Bilo, Davide
    Guala, Luciano
    Proietti, Guido
    THEORETICAL COMPUTER SCIENCE, 2012, 417 : 12 - 22