In: Discrete Mathematics, 2021, vol. 344, no. 1, p. 112169
In this work, 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 = 1 (resp. k = 2), the problem is NPhard (resp. coNPhard). We further prove that for k = 1, the problem is W[1]hard parameterized by domination number plus the mimwidth of the input...

In: Discrete Applied Mathematics, 2013, vol. 161, p. 899908
In this paper we study the complexity of generalized versions of the firefighter problem on trees, and answer several open questions of Finbow and MacGillivray (2009) [8]. More specifically, we consider the version denoted by Max (S, b)Fire where b ≥ 2 firefighters are allowed at each time step and the objective is to maximize the number of saved vertices that belong to S. We also study...

In: Discrete Applied Mathematics, 2014, vol. 178, p. 4657
A cograph is a graph which does not contain any induced path on four vertices. In this paper, we characterize those cographs that are intersection graphs of paths on a grid in the following two cases: (i) the paths on the grid all have at most one bend and the intersections concern edges (→ B1EPG); (ii) the paths on the grid are not bended and the intersections concern vertices (→...

In: European Journal of Operational Research, 2015, vol. 240, no. 2, p. 307314
In this paper we present the Selective Graph Coloring Problem, a generalization of the standard graph coloring problem as well as several of its possible applications. Given a graph with a partition of its vertex set into several clusters, we want to select one vertex per cluster such that the chromatic number of the subgraph induced by the selected vertices is minimum. This problem appeared...

In: IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2018, vol. 15, no. 1, p. 96108
Hajirasouliha and Raphael (WABI 2014) proposed a model for deconvoluting mixed tumor samples measured from a collection of highthroughput sequencing reads. This is related to understanding tumor evolution and critical cancer mutations. In short, their formulation asks to split each row of a binary matrix so that the resulting matrix corresponds to a perfect phylogeny and has the minimum number...

In: European Journal of Operational Research, 2011, vol. 210, no. 2, p. 169175
Given a graph G =(V, E), a satisfying bisection of G is a partition of the vertex set V into two sets V1, V2, such that V1 = V2, and such that every vertex v in V has at least as many neighbors in its own set as in the other set. The problem of deciding whether a graph G admits such a partition is NPcomplete. In Bazgan et al. (2008) [C. Bazgan, Z. Tuza, D. Vanderpooten, Approximation of...

In: Discrete Mathematics, 2012, vol. 312, no. 2, p. 427440
In this paper we consider graphs G whose vertices can be represented as singlebend paths (i.e., paths with at most one turn) on a rectangular grid, such that two vertices are adjacent in G if and only if the corresponding paths share at least one edge of the grid. These graphs, called B1EPG graphs, were first introduced in Golumbic et al. (2009) [13]. Here we show that the neighborhood of every...

In: Discrete Mathematics, 2012, vol. 312, no. 7, p. 13721385
The vertex colouring problem is known to be NPcomplete in the class of trianglefree graphs. Moreover, it is NPcomplete in any subclass of trianglefree graphs defined by a finite collection of forbidden induced subgraphs, each of which contains a cycle. In this paper, we study the vertex colouring problem in subclasses of trianglefree graphs obtained by forbidding graphs without cycles, i.e.,...

Public access from Jan 9, 2022
In: Theoretical Computer Science, 2020, vol. 814, p. 2848
A semitotal dominating set of a graph G with no isolated vertex is a dominating set D of G such that every vertex in D is within distance two of another vertex in D. The minimum size γt2(G) of a semitotal dominating set of G is squeezed between the domination number γ(G) and the total domination number γt(G). Semitotal Dominating Set is the problem of finding, given a graph G, a semitotal...

In: 30th International Symposium on Algorithms and Computation (ISAAC)  Leibniz International Proceedings in Informatics, 2019, vol. 149, no. 21, p. 114
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 NPhard when restricted to {P6, P4 + P2}free graphs and that it is coNPhard when restricted to subcubic clawfree graphs and 2P3free graphs. As a consequence, we are able to establish a complexity dichotomy...
