Refine my results

Specific Collection


Université de Fribourg

Reducing the domination number of graphs via edge contractions and vertex deletions

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

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 NP-hard (resp. coNP-hard). We further prove that for k = 1, the problem is W[1]-hard parameterized by domination number plus the mim-width of the input...

Université de Fribourg

The firefighter problem with more than one firefighter on trees

Bazgan, Cristina ; Chopin, Morgan ; Ries, Bernard

In: Discrete Applied Mathematics, 2013, vol. 161, p. 899-908

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...

Université de Fribourg

Characterizations of cographs as intersection graphs of paths on a grid

Cohen, Elad ; Golumbic, Martin Charles ; Ries, Bernard

In: Discrete Applied Mathematics, 2014, vol. 178, p. 46-57

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 (→ B1-EPG); (ii) the paths on the grid are not bended and the intersections concern vertices (→...

Université de Fribourg

On some applications of the selective graph coloring problem

Demange, Marc ; Ekim, Tinaz ; Ries, Bernard ; Tanasescu, Cerasela

In: European Journal of Operational Research, 2015, vol. 240, no. 2, p. 307-314

In this paper we present the Selective Graph Coloring Problem, a generalization of the standard graph col-oring 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...

Université de Fribourg

Complexity and Algorithms for Finding a Perfect Phylogeny from Mixed Tumor Samples

Hujdurovic, Ademir ; Kacar, Ursula ; Milanic, Martin ; Ries, Bernard ; Tomescu, Alexandru I.

In: IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2018, vol. 15, no. 1, p. 96-108

Hajirasouliha and Raphael (WABI 2014) proposed a model for deconvoluting mixed tumor samples measured from a collection of high-throughput 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...

Université de Fribourg

A 2-approximation for the maximum satisfying bisection problem

Ries, Bernard ; Zenklusen, Rico

In: European Journal of Operational Research, 2011, vol. 210, no. 2, p. 169-175

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 NP-complete. In Bazgan et al. (2008) [C. Bazgan, Z. Tuza, D. Vanderpooten, Approximation of...

Université de Fribourg

Some properties of edge intersection graphs of single-bend paths on a grid

Asinowski, Andrei ; Ries, Bernard

In: Discrete Mathematics, 2012, vol. 312, no. 2, p. 427-440

In this paper we consider graphs G whose vertices can be represented as single-bend 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 B1-EPG graphs, were first introduced in Golumbic et al. (2009) [13]. Here we show that the neighborhood of every...

Université de Fribourg

Colouring vertices of triangle-free graphs without forests

Dabrowski, Konrad K. ; Lozin, Vadim ; Raman, Rajiv ; Ries, Bernard

In: Discrete Mathematics, 2012, vol. 312, no. 7, p. 1372-1385

The vertex colouring problem is known to be NP-complete in the class of triangle-free graphs. Moreover, it is NP-complete in any subclass of triangle-free 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 triangle-free graphs obtained by forbidding graphs without cycles, i.e.,...

Public access from Jan 9, 2022
Université de Fribourg

Semitotal Domination: New hardness results and a polynomial-time algorithm for graphs of bounded mim-width

Galby, Esther ; Munaro, Andrea ; Ries, Bernard

In: Theoretical Computer Science, 2020, vol. 814, p. 28-48

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...

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...