Show simple item record

hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorHarutyunyan, Ararat
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorLampis, Michael
HAL ID: 182546
ORCID: 0000-0002-5791-0887
hal.structure.identifierWarwick Mathematics Institute [WMI]
dc.contributor.authorLozin, Vadim
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
dc.date.accessioned2019-12-16T15:29:21Z
dc.date.available2019-12-16T15:29:21Z
dc.date.issued2019
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/20330
dc.descriptionLecture Notes in Computer Science book series (LNCS, volume 11789)en
dc.language.isoenen
dc.subjectIndependent seten
dc.subjectSub-Cubic graphsen
dc.subjectApple-Free graphsen
dc.subject.ddc511en
dc.titleMaximum Independent Sets in Subcubic Graphs: New Resultsen
dc.typeCommunication / Conférence
dc.description.abstractenWe consider the complexity of the classical Independent Set problem on classes of subcubic graphs characterized by a finite set of forbidden induced subgraphs. It is well-known that a necessary condition for Independent Set to be tractable in such a class (unless P = NP) is that the set of forbidden induced subgraphs includes a subdivided star Sk,k,k, for some k. Here, Sk,k,kis the graph obtained by taking three paths of length k and identifying one of their endpoints.It is an interesting open question whether this condition is also sufficient: is Independent Set tractable on all hereditary classes of subcubic graphs that exclude some Sk,k,k? A positive answer to this question would provide a complete classification of the complexity of Independent Set on all classes of subcubic graphs characterized by a finite set of forbidden induced subgraphs. The best currently known result of this type is tractability for S2,2,2-free graphs. In this paper we generalize this result by showing that the problem remains tractable on S2,k,k-free graphs, for any fixed k. Along the way, we show that subcubic Independent Set is tractable for graphs excluding a type of graph we call an “apple with a long stem”, generalizing known results for apple-free graphs.en
dc.identifier.citationpages40-52en
dc.relation.ispartoftitleGraph-Theoretic Concepts in Computer Science, Revised Papersen
dc.relation.ispartofeditorSau, Ignasi
dc.relation.ispartofeditorThilikos, Dimitrios M.
dc.relation.ispartofpublnameSpringer International Publishingen
dc.relation.ispartofpublcityBerlin Heidelbergen
dc.relation.ispartofdate2019
dc.relation.ispartofpages394en
dc.relation.ispartofurl10.1007/978-3-030-30786-8en
dc.subject.ddclabelPrincipes généraux des mathématiquesen
dc.relation.ispartofisbn978-3-030-30785-1en
dc.relation.conftitle45th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2019)en
dc.relation.confdate2019-06
dc.relation.confcityVall de Núriaen
dc.relation.confcountrySpainen
dc.relation.forthcomingnonen
dc.identifier.doi10.1007/978-3-030-30786-8_4en
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2019-12-16T15:15:59Z
hal.faultCode{"duplicate-entry":{"hal-02344055":{"doi":"1.0"}}}
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