Université de Fribourg

Blocking Total Dominating Sets Via Edge Contractions

Galby, Esther ; Mann, Felix ; Ries, Bernard

In: Theoretical Computer Science, 2021, vol. 877, p. 18-35

In this paper, we study the problem of deciding whether the total domination number of a given graph Gcan be reduced using exactly one edge contraction (called1-Edge Contraction(γt)). We focus on several graph classes and determine the computational complexity of this problem. By putting together these results, we manage to obtain a complete complexity dichotomy for H-free graphs.

Université de Fribourg

Blocking Dominating Sets for H-Free Graphs via Edge Contractions

Galby, Esther ; Lima, Paloma T. ; Ries, Bernard

In: 30th International Symposium on Algorithms and Computation (ISAAC) - Leibniz International Proceedings in Informatics, 2019, vol. 149, no. 21, p. 1-14

In this paper, we consider the following problem: given a connected graph G, can we reduce the domination number of G by one by using only one edge contraction? We show that the problem is NP-hard when restricted to {P6, P4 + P2}-free graphs and that it is coNP-hard when restricted to subcubic claw-free graphs and 2P3-free graphs. As a consequence, we are able to establish a complexity dichotomy...

Université de Fribourg

Contraction and deletion blockers for perfect graphs and H-free graphs

Y. Diner, Öznur ; Paulusma, Daniël ; Picouleau, Christophe ; Ries, Bernard

In: Theoretical computer science, 2018, vol. 746, p. 49-72

We study the following problem: for given integers d, k and graph G, can we reduce some fixed graph parameter π of G by at least d via at most k graph operations from some fixed set S? As parameters we take the chromatic number χ, clique number ω and independence number α, and as operations we choose edge contraction ec and vertex deletion vd. We determine the complexity of this problem...