• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail

Maximum Independent Sets in Subcubic Graphs: New Results

Harutyunyan, Ararat; Lampis, Michael; Lozin, Vadim; Monnot, Jérôme (2019), Maximum Independent Sets in Subcubic Graphs: New Results, Graph-Theoretic Concepts in Computer Science, 45th International Workshop, WG 2019, 2019

View/Open
1810.10940.pdf (220.4Kb)
Type
Communication / Conférence
Date
2019
Conference title
Graph-Theoretic Concepts in Computer Science, 45th International Workshop, WG 2019
Conference date
2019
Book author
Ignasi Sau, Dimitrios M. Thilikos
Publisher
Springer International Publishing
Published in
Berlin Heidelberg
ISBN
978-3-030-30785-1;978-3-030-30786-8
Pages
40-52
Publication identifier
10.1007/978-3-030-30786-8_4
Metadata
Show full item record
Author(s)
Harutyunyan, Ararat
Lampis, Michael cc
Lozin, Vadim
Monnot, Jérôme cc
Abstract (EN)
We 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.
Subjects / Keywords
Independent set; Sub-Cubic graphs; Apple-Free graphs

Related items

Showing items related by title and author.

  • Thumbnail
    Maximum Independent Sets in Subcubic Graphs: New Results 
    Harutyunyan, Ararat; Lampis, Michael; Lozin, Vadim; Monnot, Jérôme (2019) Communication / Conférence
  • Thumbnail
    Maximum independent sets in subcubic graphs: New results 
    Harutyunyan, Ararat; Lampis, Michael; Lozin, V.; Monnot, Jérôme (2020) Article accepté pour publication ou publié
  • Thumbnail
    On the maximum independent set problem in subclasses of subcubic graphs 
    Ries, Bernard; Monnot, Jérôme; Lozin, Vadim (2015) Article accepté pour publication ou publié
  • Thumbnail
    On the Maximum Independent Set Problem in Subclasses of Subcubic Graphs 
    Lozin, Vadim; Monnot, Jérôme; Ries, Bernard (2013) Communication / Conférence
  • Thumbnail
    Extension of Vertex Cover and Independent Set in Some Classes of Graphs 
    Casel, Katrin; Fernau, Henning; Khosravian Ghadikolaei, Mehdi; Monnot, Jérôme; Sikora, Florian (2019) Communication / Conférence
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo