Show simple item record

dc.contributor.authorHarutyunyan, Ararat
dc.contributor.authorLampis, Michael
dc.contributor.authorLozin, Vadim
dc.contributor.authorMonnot, Jérôme
dc.date.accessioned2020-01-27T15:46:07Z
dc.date.available2020-01-27T15:46:07Z
dc.date.issued2019
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/20483
dc.language.isoenen
dc.subjectIndependent set
dc.subjectSub-Cubic graphs
dc.subjectApple-Free graphs
dc.subject.ddc003en
dc.titleMaximum Independent Sets in Subcubic Graphs: New Results
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,k is 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.
dc.identifier.citationpages40-52
dc.relation.ispartofeditorIgnasi Sau, Dimitrios M. Thilikos
dc.relation.ispartofpublnameSpringer International Publishing
dc.relation.ispartofpublcityBerlin Heidelberg
dc.relation.ispartofurl10.1007/978-3-030-30786-8
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-3-030-30785-1;978-3-030-30786-8
dc.relation.conftitleGraph-Theoretic Concepts in Computer Science, 45th International Workshop, WG 2019
dc.relation.confdate2019
dc.relation.forthcomingnonen
dc.identifier.doi10.1007/978-3-030-30786-8_4
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.date.updated2020-06-11T09:17:13Z
hal.person.labIds989
hal.person.labIds989
hal.person.labIds41505
hal.person.labIds989
hal.faultCode{"duplicate-entry":{"hal-02344055":{"doi":"1.0"}}}


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record