Show simple item record

hal.structure.identifierTheoretical Computer Science, University of Trier, Germany
dc.contributor.authorCasel, Katrin*
hal.structure.identifierTheoretical Computer Science, University of Trier, Germany
dc.contributor.authorFernau, Henning*
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorKhosravian Ghadikolaei, Mehdi*
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorMonnot, Jérôme
HAL ID: 178759
ORCID: 0000-0002-7452-6553
*
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorSikora, Florian
HAL ID: 742949
ORCID: 0000-0003-2670-6258
*
dc.date.accessioned2019-07-16T10:29:49Z
dc.date.available2019-07-16T10:29:49Z
dc.date.issued2019
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/19243
dc.descriptionLecture Notes in Computer Science book series (LNCS, volume 11485)en
dc.language.isoenen
dc.subjectExtension problemsen
dc.subjectSpecial graph classesen
dc.subjectApproximation algorithmsen
dc.subjectNP-completenessen
dc.subject.ddc519en
dc.titleExtension of Vertex Cover and Independent Set in Some Classes of Graphsen
dc.typeCommunication / Conférence
dc.description.abstractenWe study extension variants of the classical problems Vertex Cover and Independent Set. Given a graph G=(V,E) and a vertex set U⊆V, it is asked if there exists a minimal vertex cover (resp. maximal independent set) S with U⊆S (resp. U⊇S). Possibly contradicting intuition, these problems tend to be NP-complete, even in graph classes where the classical problem can be solved efficiently. Yet, we exhibit some graph classes where the extension variant remains polynomial-time solvable. We also study the parameterized complexity of theses problems, with parameter |U|, as well as the optimality of simple exact algorithms under ETH. All these complexity considerations are also carried out in very restricted scenarios, be it degree or topological restrictions (bipartite, planar or chordal graphs). This also motivates presenting some explicit branching algorithms for degree-bounded instances. e further discuss the price of extension, measuring the distance of U to the closest set that can be extended, which results in natural optimization problems related to extension problems for which we discuss polynomial-time approximability.en
dc.identifier.citationpages124-136en
dc.relation.ispartoftitleAlgorithms and Complexityen
dc.relation.ispartofeditorHeggernes, Pinar
dc.relation.ispartofpublnameSpringer International Publishingen
dc.relation.ispartofpublcityBerlin Heidelbergen
dc.relation.ispartofdate2019
dc.relation.ispartofpages378en
dc.relation.ispartofurl10.1007/978-3-030-17402-6en
dc.subject.ddclabelProbabilités et mathématiques appliquéesen
dc.relation.ispartofisbn978-3-030-17401-9;978-3-030-17402-6en
dc.relation.conftitle11th International Conference, CIAC 2019en
dc.relation.confdate2019-05
dc.relation.confcityRomeen
dc.relation.confcountryItalyen
dc.relation.forthcomingnonen
dc.identifier.doi10.1007/978-3-030-17402-6_11en
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2019-07-16T10:26:44Z
hal.identifierhal-02184942*
hal.version1*
hal.update.actionupdateFiles*
hal.update.actionupdateMetadata*
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record