• 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

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), Extension of Vertex Cover and Independent Set in Some Classes of Graphs, in Heggernes, Pinar, Algorithms and Complexity, Springer International Publishing : Berlin Heidelberg, p. 124-136. 10.1007/978-3-030-17402-6_11

View/Open
Extension_vertex.pdf (269.1Kb)
Type
Communication / Conférence
Date
2019
Conference title
11th International Conference, CIAC 2019
Conference date
2019-05
Conference city
Rome
Conference country
Italy
Book title
Algorithms and Complexity
Book author
Heggernes, Pinar
Publisher
Springer International Publishing
Published in
Berlin Heidelberg
ISBN
978-3-030-17401-9;978-3-030-17402-6
Number of pages
378
Pages
124-136
Publication identifier
10.1007/978-3-030-17402-6_11
Metadata
Show full item record
Author(s)
Casel, Katrin
Theoretical Computer Science, University of Trier, Germany
Fernau, Henning
Theoretical Computer Science, University of Trier, Germany
Khosravian Ghadikolaei, Mehdi
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Monnot, Jérôme cc
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Sikora, Florian cc
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
We 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.
Subjects / Keywords
Extension problems; Special graph classes; Approximation algorithms; NP-completeness

Related items

Showing items related by title and author.

  • Thumbnail
    Extension of Some Edge Graph Problems: Standard and Parameterized Complexity 
    Casel, Katrin; Fernau, Henning; Khosravian Ghadikolaei, Mehdi; Monnot, Jérôme; Sikora, Florian (2019) Communication / Conférence
  • Thumbnail
    On the complexity of solution extension of optimization problems 
    Sikora, Florian; Casel, Katrin; Fernau, Henning; Khosravian Ghadikolaei, Mehdi; Monnot, Jérôme (2020) Article accepté pour publication ou publié
  • Thumbnail
    Abundant Extensions 
    Casel, Katrin; Fernau, Henning; Khosravian Ghadikolaei, Mehdi; Monnot, Jérôme; Sikora, Florian (2021) Communication / Conférence
  • Thumbnail
    Extension and its price for the connected vertex cover problem 
    Khosravian Ghadikolaei, Mehdi; Melissinos, Nikolaos; Monnot, Jérôme; Pagourtzis, Aris (2019) Communication / Conférence
  • Thumbnail
    Weighted Upper Edge Cover: Complexity and Approximability 
    Khoshkhah, Kaveh; 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