
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
Type
Communication / ConférenceDate
2019Conference title
11th International Conference, CIAC 2019Conference date
2019-05Conference city
RomeConference country
ItalyBook title
Algorithms and ComplexityBook author
Heggernes, PinarPublisher
Springer International Publishing
Published in
Berlin Heidelberg
ISBN
978-3-030-17401-9;978-3-030-17402-6
Number of pages
378Pages
124-136
Publication identifier
Metadata
Show full item recordAuthor(s)
Casel, KatrinTheoretical 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

Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Sikora, Florian

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-completenessRelated items
Showing items related by title and author.
-
Casel, Katrin; Fernau, Henning; Khosravian Ghadikolaei, Mehdi; Monnot, Jérôme; Sikora, Florian (2019) Communication / Conférence
-
Sikora, Florian; Casel, Katrin; Fernau, Henning; Khosravian Ghadikolaei, Mehdi; Monnot, Jérôme (2020) Article accepté pour publication ou publié
-
Casel, Katrin; Fernau, Henning; Khosravian Ghadikolaei, Mehdi; Monnot, Jérôme; Sikora, Florian (2021) Communication / Conférence
-
Khosravian Ghadikolaei, Mehdi; Melissinos, Nikolaos; Monnot, Jérôme; Pagourtzis, Aris (2019) Communication / Conférence
-
Khosravian Ghadikolaei, Mehdi; Melissinos, Nikolaos; Monnot, Jérôme; Pagourtzis, Aris (2022) Article accepté pour publication ou publié