Conference paper (in proceedings)
Reducing the Domination Number of Graphs via Edge Contractions
Published in:
 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)  LIPICS Vol. 138 / Rossmanith, Peter ; Heggernes, Pinar ; Katoen,JoostPieter.  Schloss Dagstuhl  LeibnizZentrum fuer Informatik GmbH.  2019, p. 41:141:13
English
In this paper, we study the following problem: given a connected graph G, can we reduce the domination number of G by at least one using k edge contractions, for some fixed integer k >= 0? We show that for k <= 2, the problem is coNPhard. We further prove that for k=1, the problem is W[1]hard parameterized by the size of a minimum dominating set plus the mimwidth of the input graph, and that it remains NPhard when restricted to P_9free graphs, bipartite graphs and {C_3,...,C_{l}}free graphs for any l >= 3. Finally, we show that for any k >= 1, the problem is polynomialtime solvable for P_5free graphs and that it can be solved in FPTtime and XPtime when parameterized by treewidth and mimwidth, respectively.

Faculty
 Faculté des sciences économiques et sociales

Department
 Département d'informatique

Language


Classification

Computer science

License

License undefined

Identifiers


Persistent URL

https://folia.unifr.ch/unifr/documents/308092
Statistics
Document views: 8
File downloads: