• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

Maximum Independent Sets in Subcubic Graphs: New Results

Thumbnail
View/Open
1810.10940.pdf (220.4Kb)
Date
2019
Notes
Lecture Notes in Computer Science book series (LNCS, volume 11789)
Dewey
Principes généraux des mathématiques
Sujet
Independent set; Sub-Cubic graphs; Apple-Free graphs
DOI
http://dx.doi.org/10.1007/978-3-030-30786-8_4
Conference name
45th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2019)
Conference date
06-2019
Conference city
Vall de Núria
Conference country
Spain
Book title
Graph-Theoretic Concepts in Computer Science, Revised Papers
Author
Sau, Ignasi; Thilikos, Dimitrios M.
Publisher
Springer International Publishing
Publisher city
Berlin Heidelberg
Year
2019
Pages number
394
ISBN
978-3-030-30785-1
Book URL
10.1007/978-3-030-30786-8
URI
https://basepub.dauphine.fr/handle/123456789/20330
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Harutyunyan, Ararat
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Lampis, Michael
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Lozin, Vadim
41505 Warwick Mathematics Institute [WMI]
Monnot, Jérôme
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Type
Communication / Conférence
Item number of pages
40-52
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,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.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.