BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Bernard Ries

Bernard Ries contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Discrete MathematicsComputational ComplexityData Structures and Algorithmsmath.COComputational Geometry

Trust snapshot

Quick read

Trust 19 - UnverifiedVerification L1Unclaimed author
5works
0followers
5topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

Published work

5 published item(s)

preprint2022arXiv

Finding Matching Cuts in $H$-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 $H$-free graphs, that is, graphs that do not contain some fixed graph $H$ as an induced subgraph. We also prove new complexity results for two recently studied variants of Matching Cut, on $H$-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>0$ such that the first variant is NP-complete for $P_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 $H$-free graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Locally checkable problems parameterized by clique-width

We continue the study initiated by Bonomo-Braberman and Gonzalez in 2020 on $r$-locally checkable problems. We propose a dynamic programming algorithm that takes as input a graph with an associated clique-width expression and solves a $1$-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]-$Roman domination problem is FPT, and the $k$-community problem, Max PDS and other variants are XP.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

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

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

0 citations0 reviewsNo code linkedOpen 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 $k$ bends for some $k \geq 0$, the graph is said to be $B_k$-CPG. We first show that, for any $k \geq 0$, the class of $B_k$-CPG graphs is strictly contained in the class of $B_{k+1}$-CPG graphs even within the class of planar graphs, thus implying that there exists no $k \geq 0$ such that every planar CPG graph is $B_k$-CPG. The main result of the paper is that recognizing CPG graphs and $B_k$-CPG graphs with $k \geq 1$ is $\mathsf{NP}$-complete. Moreover, we show that the same remains true even within the class of planar graphs in the case $k \geq 3$. We then consider several graph problems restricted to CPG graphs and show, in particular, that Independent Set and Clique Cover remain $\mathsf{NP}$-hard for $B_0$-CPG graphs. Finally, we consider the related classes $B_k$-EPG of edge-intersection graphs of paths with at most $k$ bends on a grid. Although it is possible to optimally color a $B_0$-EPG graph in polynomial time, as this class coincides with that of interval graphs, we show that, in contrast, 3-Colorability is $\mathsf{NP}$-complete for $B_1$-EPG graphs.

0 citations0 reviewsNo code linkedOpen access