
Extension of Some Edge Graph Problems: Standard and Parameterized Complexity
Casel, Katrin; Fernau, Henning; Khosravian Ghadikolaei, Mehdi; Monnot, Jérôme; Sikora, Florian (2019), Extension of Some Edge Graph Problems: Standard and Parameterized Complexity, in Leszek Antoni Gąsieniec, Jesper Jansson, Christos Levcopoulos, Fundamentals of Computation Theory: 22nd International Symposium, FCT 2019, Springer International Publishing : Berlin Heidelberg, p. 185-200. 10.1007/978-3-030-25027-0_13
View/ Open
Type
Communication / ConférenceDate
2019Conference date
2019Book title
Fundamentals of Computation Theory: 22nd International Symposium, FCT 2019Book author
Leszek Antoni Gąsieniec, Jesper Jansson, Christos LevcopoulosPublisher
Springer International Publishing
Published in
Berlin Heidelberg
ISBN
978-3-030-25026-3;978-3-030-25027-0
Pages
185-200
Publication identifier
Metadata
Show full item recordAuthor(s)
Casel, KatrinHasso Plattner Institute (HPI)
Fernau, Henning
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 consider extension variants of some edge optimization problems in graphs containing the classical Edge Cover, Matching, and Edge Dominating Set problems. Given a graph G=(V,E) and an edge set U⊆E, it is asked whether there exists an inclusion-wise minimal (resp., maximal) feasible solution E′ which satisfies a given property, for instance, being an edge dominating set (resp., a matching) and containing the forced edge set U (resp., avoiding any edges from the forbidden edge set E∖U). We present hardness results for these problems, for restricted instances such as bipartite or planar graphs. We counter-balance these negative results with parameterized complexity results. We also consider the price of extension, a natural optimization problem variant of extension problems, leading to some approximation results.Subjects / Keywords
Extension problems; Edge cover; Matching; Edge domination; NP-completeness; Parameterized complexity; ApproximationRelated 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
-
Khoshkhah, Kaveh; Khosravian Ghadikolaei, Mehdi; Monnot, Jérôme; Sikora, Florian (2019) Communication / Conférence
-
Khoshkhah, Kaveh; Khosravian Ghadikolaei, Mehdi; Monnot, Jérôme; Sikora, Florian (2020) Article accepté pour publication ou publié