On the approximability of some degree-constrained subgraph problems
- Others:
- Département de Mathématiques et Applications - ENS Paris (DMA) ; École normale supérieure - Paris (ENS-PSL) ; Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)
- Department of Computer Science and Applied Mathematics [Rehovot] ; Weizmann Institute of Science [Rehovot, Israël]
- Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE) ; Inria Sophia Antipolis - Méditerranée (CRISAM) ; Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED) ; Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S) ; Université Nice Sophia Antipolis (1965 - 2019) (UNS) ; COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS) ; COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S) ; Université Nice Sophia Antipolis (1965 - 2019) (UNS) ; COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS) ; COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)
- Algorithmes, Graphes et Combinatoire (ALGCO) ; Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM) ; Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)
- Institute of Mathematical Sciences [Chennai] (IMSc)
Description
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 Maximumd-degree-bounded Connected Subgraph (MDBCS"d) problem takes as additional input a weight function @w:E->R^+, and asks for a subset E^'@?E such that the subgraph induced by E^' is connected, has maximum degree at most d, and @?"e"@?"E"^"'@w(e) is maximized. The Minimum Subgraph of Minimum Degree>=d (MSMD"d) problem involves finding a smallest subgraph of G with minimum degree at least d. Finally, the Dual Degree-densek-Subgraph (DDDkS) problem consists in finding a subgraph H of G such that |V(H)|@?k and the minimum degree in H is maximized.
Abstract
International audience
Additional details
- URL
- https://hal-lirmm.ccsd.cnrs.fr/lirmm-00736702
- URN
- urn:oai:HAL:lirmm-00736702v1
- Origin repository
- UNICA