HAL TEI export of lirmm-00744655v3 CCSD CC0 1.0 - Universal

HAL API Platform

 NP-hardness of the Sparsest k-Subgraph Problem in Chordal Graphs Rémi Watrigant 4f2192d2030f8cf751190a5cfc3c2a9e univ-lyon1.fr remi-watrigant 171721 34513-171721 https://www.idref.fr/199341230 https://orcid.org/0000-0002-6243-5910 Marin Bougeret 866ea4828811774358e36f187ffc2c9c imag.fr marin-bougeret 10167 17678-10167 https://orcid.org/0000-0002-9910-4656 https://www.idref.fr/197511686 Rodolphe Giroudeau 3eafab1248c9498dcf1c870a3b621a56 lirmm.fr rodolphe-giroudeau 172373 17662-172373 https://www.idref.fr/095605355 Rémi Watrigant 7e513965d7054f0c7d961f116078147e lirmm.fr 2012-10-23 15:32:43 2013-05-29 09:32:56 2013-06-07 10:37:00 2023-03-24 14:52:57 2013-06-10 14:38:49 2012-10-23 2013-06-07 contributor Rémi Watrigant 7e513965d7054f0c7d961f116078147e lirmm.fr CCSD lirmm-00744655 https://hal-lirmm.ccsd.cnrs.fr/lirmm-00744655 watrigant:lirmm-00744655 RR-12026, 2012 RR-12026, 2012 HAL Authorization CNRS - Centre national de la recherche scientifique Méthodes Algorithmes pour l'Ordonnancement et les Réseaux Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier LARA Mathématiques, Informatique, Physique et Systèmes Université de Montpellier Université de Montpellier (2015-2021) Not set NP-hardness of the Sparsest k-Subgraph Problem in Chordal Graphs Rémi Watrigant 4f2192d2030f8cf751190a5cfc3c2a9e univ-lyon1.fr remi-watrigant 171721 34513-171721 https://www.idref.fr/199341230 https://orcid.org/0000-0002-6243-5910 Marin Bougeret 866ea4828811774358e36f187ffc2c9c imag.fr marin-bougeret 10167 17678-10167 https://orcid.org/0000-0002-9910-4656 https://www.idref.fr/197511686 Rodolphe Giroudeau 3eafab1248c9498dcf1c870a3b621a56 lirmm.fr rodolphe-giroudeau 172373 17662-172373 https://www.idref.fr/095605355 RR-12026 2012-10-23 English Computer Science [cs]/Data Structures and Algorithms [cs.DS] Reports Reports Reports

Given a simple undirected graph G = (V,E) and an integer k ≤ |V|, the k-sparsest subgraph problem asks for a set of k vertices which induce the minimum number of edges. Whereas its special case independent set and many other optimization problems become polynomial-time solvable in chordal graphs, we show that k-sparsest subgraph remains NP-hard in this graph class.

 Methods, Algorithms for Operations REsearch MAORE 2021-12-31
LIRMM, 161 rue Ada, 34000 Montpellier
https://www.lirmm.fr/equipes/MAORE/ 139590827 0000000405990488 199111950H https://ror.org/013yean28 Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier LIRMM 1995-01-01 2021-12-31
161 rue Ada - 34095 Montpellier
https://www.lirmm.fr 0000000120970141 https://ror.org/051escj72 Université de Montpellier UM 2021-12-31
163 rue Auguste Broussonnet - 34090 Montpellier
http://www.umontpellier.fr/ 02636817X 0000000122597504 https://ror.org/02feahw73 Centre National de la Recherche Scientifique CNRS 1939-10-19
https://www.cnrs.fr/