BZPEER
More

Discover

About BZPEERSearchGraph

Research tools

HomeCollectionsResearchCollaborationPublish

Network

ExpertsCommunities

Opportunities

Listings

Account

Log inCreate account
Log inCreate account

Source author record

Bernard Ries

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record
Discrete MathematicsData Structures and AlgorithmsComputational Complexitymath.COComputational GeometryPopulations and Evolution

Catalog footprint

Research overview

9works
6topics
4close collaborators

Actions

Is this your work?

Log in to claim
Open graphBrowse papers

Published work

9 publications

preprint2022arXiv

Finding Matching Cuts in HH-Free Graphs

The NP-complete problem Matching Cut is to decide if a graph has a matching that is also an edge cut of the graph. We prove new complexity results for Matching Cut restricted to HH-free graphs, that is, graphs that do not contain some fixed graph HH as an induced subgraph. We also prove new complexity results for two recently studied variants of Matching Cut, on HH-free graphs. The first variant requires that the matching cut must be extendable to a perfect matching of the graph. The second variant requires the matching cut to be a perfect matching. In particular, we prove that there exists a small constant r>0r>0 such that the first variant is NP-complete for PrP_r-free graphs. This addresses a question of Bouquet and Picouleau (arXiv, 2020). For all three problems, we give state-of-the-art summaries of their computational complexity for HH-free graphs.

Open access
preprint2022arXiv

Locally checkable problems parameterized by clique-width

We continue the study initiated by Bonomo-Braberman and Gonzalez in 2020 on rr-locally checkable problems. We propose a dynamic programming algorithm that takes as input a graph with an associated clique-width expression and solves a 11-locally checkable problem under certain restrictions. We show that it runs in polynomial time in graphs of bounded clique-width, when the number of colors of the locally checkable problem is fixed. Furthermore, we present a first extension of our framework to global properties by taking into account the sizes of the color classes, and consequently enlarge the set of problems solvable in polynomial time with our approach in graphs of bounded clique-width. As examples, we apply this setting to show that, when parameterized by clique-width, the [k]−[k]-Roman domination problem is FPT, and the kk-community problem, Max PDS and other variants are XP.

Open access
preprint2022arXiv

On The Complexity of Matching Cut for Graphs of Bounded Radius and HH-Free Graphs

For a connected graph G=(V,E)G=(V,E), a matching M⊆EM\subseteq E is a matching cut of GG if G−MG-M is disconnected. It is known that for an integer dd, the corresponding decision problem Matching Cut is polynomial-time solvable for graphs of diameter at most dd if d≤2d\leq 2 and NP-complete if d≥3d\geq 3. We prove the same dichotomy for graphs of bounded radius. For a graph HH, a graph is HH-free if it does not contain HH as an induced subgraph. As a consequence of our result, we can solve Matching Cut in polynomial time for P6P_6-free graphs, extending a recent result of Feghali for P5P_5-free graphs. We then extend our result to hold even for (sP3+P6)(sP_3+P_6)-free graphs for every s≥0s\geq 0 and initiate a complexity classification of Matching Cut for HH-free graphs.

Open access
preprint2020arXiv

CPG graphs: Some structural and hardness results

In this paper we continue the systematic study of Contact graphs of Paths on a Grid (CPG graphs) initiated in [Deniz et al., 2018]. A CPG graph is a graph for which there exists a collection of pairwise interiorly disjoint paths on a grid in one-to-one correspondence with its vertex set such that two vertices are adjacent if and only if the corresponding paths touch at a grid-point. If every such path has at most kk bends for some k≥0k \geq 0, the graph is said to be BkB_k-CPG. We first show that, for any k≥0k \geq 0, the class of BkB_k-CPG graphs is strictly contained in the class of Bk+1B_{k+1}-CPG graphs even within the class of planar graphs, thus implying that there exists no k≥0k \geq 0 such that every planar CPG graph is BkB_k-CPG. The main result of the paper is that recognizing CPG graphs and BkB_k-CPG graphs with k≥1k \geq 1 is NP\mathsf{NP}-complete. Moreover, we show that the same remains true even within the class of planar graphs in the case k≥3k \geq 3. We then consider several graph problems restricted to CPG graphs and show, in particular, that Independent Set and Clique Cover remain NP\mathsf{NP}-hard for B0B_0-CPG graphs. Finally, we consider the related classes BkB_k-EPG of edge-intersection graphs of paths with at most kk bends on a grid. Although it is possible to optimally color a B0B_0-EPG graph in polynomial time, as this class coincides with that of interval graphs, we show that, in contrast, 3-Colorability is NP\mathsf{NP}-complete for B1B_1-EPG graphs.

Open access
preprint2016arXiv

Complexity and algorithms for finding a perfect phylogeny from mixed tumor samples

Recently, 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 of rows among all matrices with this property. In this paper we disprove several claims about this problem, including an NP-hardness proof of it. However, we show that the problem is indeed NP-hard, by providing a different proof. We also prove NP-completeness of a variant of this problem proposed in the same paper. On the positive side, we propose an efficient (though not necessarily optimal) heuristic algorithm based on coloring co-comparability graphs, and a polynomial time algorithm for solving the problem optimally on matrix instances in which no column is contained in both columns of a pair of conflicting columns. Implementations of these algorithms are freely available at https://github.com/alexandrutomescu/MixedPerfectPhylogeny

Open access
preprint2016arXiv

Upper Domination: towards a dichotomy through boundary properties

An upper dominating set in a graph is a minimal (with respect to set inclusion) dominating set of maximum cardinality. The problem of finding an upper dominating set is generally NP-hard. We study the complexity of this problem in classes of graphs defined by finitely many forbidden induced subgraphs and conjecture that the problem admits a dichotomy in this family, i.e. it is either NP-hard or polynomial-time solvable for each class in the family. A helpful tool to study the complexity of an algorithmic problem on finitely defined classes of graphs is the notion of boundary classes. However, none of such classes has been identified so far for the upper dominating set problem. In the present paper, we discover the first boundary class for this problem and prove the dichotomy for classes defined by a single forbidden induced subgraph.

Open access
preprint2015arXiv

Dominating induced matchings in graphs containing no long claw

An induced matching MM in a graph GG is dominating if every edge not in MM shares exactly one vertex with an edge in MM. The dominating induced matching problem (also known as efficient edge domination) asks whether a graph GG contains a dominating induced matching. This problem is generally NP-complete, but polynomial-time solvable for graphs with some special properties. In particular, it is solvable in polynomial time for claw-free graphs. In the present paper, we study this problem for graphs containing no long claw, i.e. no induced subgraph obtained from the claw by subdividing each of its edges exactly once. To solve the problem in this class, we reduce it to the following question: given a graph GG and a subset of its vertices, does GG contain a matching saturating all vertices of the subset? We show that this question can be answered in polynomial time, thus providing a polynomial-time algorithm to solve the dominating induced matching problem for graphs containing no long claw.

Open access
preprint2011arXiv

The firefighter problem with more than one firefighter on trees

In this paper we study the complexity of the firefighter problem and related problems on trees when more than one firefighter is available at each time step, and answer several open questions of Finbow and MacGillivray 2009. More precisely, when b≥2b \geq 2 firefighters are allowed at each time step, the problem is NP-complete for trees of maximum degree b+2b+2 and polynomial-time solvable for trees of maximum degree b+2b+2 when the fire breaks out at a vertex of degree at most b+1b+1. Moreover we present a polynomial-time algorithm for a subclass of trees, namely kk-caterpillars.

Open access

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.