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), 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érence
Date
2019
Conference date
2019
Book title
Fundamentals of Computation Theory: 22nd International Symposium, FCT 2019
Book author
Leszek Antoni Gąsieniec, Jesper Jansson, Christos Levcopoulos
Publisher
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 record
Author(s)
Casel, Katrin

Hasso 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 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 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; Approximation