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

Raffaele Mosca

Raffaele Mosca contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Discrete Mathematicsmath.COComputer Science and Game Theoryecon.GNq-fin.EC

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
12works
0followers
5topics
2close 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

12 published item(s)

preprint2022arXiv

A note on hospital financing: local financing vs. central financing

This note tries to study how hospital behaviors, with reference to interhospital collaboration or competition, could be affected by hospital financing systems. For that this note simulates two scenarios which start with the following baseline scenario: a State, with a set of hospitals, each with all types of wards at a basic level. The evolution of this baseline scenario consists in the evolution of hospitals, that is, in the possibility of hospitals to make some of their wards excel. The State has a budget, for the evolution of this baseline scenario, which can be used by two financing systems: either by a "local financing", i.e., by splitting the budget among the hospitals so that each hospital is managing its own portion of the budget by pursuing the individual benefit, or by a "central financing", i.e., by not splitting the budget among the hospitals so that the State is the sole manager of the budget, by pursuing the benefit of the whole community. The conclusions seem to be that: in the local financing system hospitals tend to diversify their excellences, while in the central financing system the State tends to create poles of excellence.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Finding Efficient Domination for $S_{1,3,3}$-Free Bipartite Graphs in Polynomial Time

A vertex set $D$ in a finite undirected graph $G$ is an {\em efficient dominating set} (\emph{e.d.s.}\ for short) of $G$ if every vertex of $G$ is dominated by exactly one vertex of $D$. The \emph{Efficient Domination} (ED) problem, which asks for the existence of an e.d.s.\ in $G$, is \NP-complete for various $H$-free bipartite graphs, e.g., Lu and Tang showed that ED is \NP-complete for chordal bipartite graphs and for planar bipartite graphs; actually, ED is \NP-complete even for planar bipartite graphs with vertex degree at most 3 and girth at least $g$ for every fixed $g$. Thus, ED is \NP-complete for $K_{1,4}$-free bipartite graphs and for $C_4$-free bipartite graphs. In this paper, we show that ED can be solved in polynomial time for $S_{1,3,3}$-free bipartite graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Finding Dominating Induced Matchings in $(S_{2,2,3})$-Free Graphs in Polynomial Time

Let $G=(V,E)$ be a finite undirected graph. An edge set $E' \subseteq E$ is a {\em dominating induced matching} ({\em d.i.m.}) in $G$ if every edge in $E$ is intersected by exactly one edge of $E'$. The \emph{Dominating Induced Matching} (\emph{DIM}) problem asks for the existence of a d.i.m.\ in $G$; this problem is also known as the \emph{Efficient Edge Domination} problem; it is the Efficient Domination problem for line graphs. The DIM problem is \NP-complete even for very restricted graph classes such as planar bipartite graphs with maximum degree 3 and is solvable in linear time for $P_7$-free graphs, and in polynomial time for $S_{1,2,4}$-free graphs as well as for $S_{2,2,2}$-free graphs. In this paper, combining two distinct approaches, we solve it in polynomial time for $S_{2,2,3}$-free graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Finding Dominating Induced Matchings in $P_9$-Free Graphs in Polynomial Time

Let $G=(V,E)$ be a finite undirected graph. An edge subset $E' \subseteq E$ is a {\em dominating induced matching} ({\em d.i.m.}) in $G$ if every edge in $E$ is intersected by exactly one edge of $E'$. The \emph{Dominating Induced Matching} (\emph{DIM}) problem asks for the existence of a d.i.m.\ in $G$. The DIM problem is \NP-complete even for very restricted graph classes such as planar bipartite graphs with maximum degree 3 but was solved in linear time for $P_7$-free graphs and in polynomial time for $P_8$-free graphs. In this paper, we solve it in polynomial time for $P_9$-free graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Finding Dominating Induced Matchings in $S_{1,1,5}$-Free Graphs in Polynomial Time

Let $G=(V,E)$ be a finite undirected graph. An edge set $E' \subseteq E$ is a {\em dominating induced matching} ({\em d.i.m.}) in $G$ if every edge in $E$ is intersected by exactly one edge of $E'$. The \emph{Dominating Induced Matching} (\emph{DIM}) problem asks for the existence of a d.i.m.\ in $G$; this problem is also known as the \emph{Efficient Edge Domination} problem; it is the Efficient Domination problem for line graphs. The DIM problem is \NP-complete even for very restricted graph classes such as planar bipartite graphs with maximum degree 3 but is solvable in linear time for $P_7$-free graphs, and in polynomial time for $S_{1,2,4}$-free graphs as well as for $S_{2,2,2}$-free graphs and for $S_{2,2,3}$-free graphs. In this paper, combining two distinct approaches, we solve it in polynomial time for $S_{1,1,5}$-free graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Independent sets in ($P_4+P_4$,Triangle)-free graphs

The Maximum Weight Independent Set Problem (WIS) is a well-known NP-hard problem. A popular way to study WIS is to detect graph classes for which WIS can be solved in polynomial time, with particular reference to hereditary graph classes, i.e., defined by a hereditary graph property or equivalently by forbidding one or more induced subgraphs. Given two graphs $G$ and $H$, $G+H$ denotes the disjoint union of $G$ and $H$. This manuscript shows that (i) WIS can be solved for ($P_4+P_4$, Triangle)-free graphs in polynomial time, where a $P_4$ is an induced path of four vertices and a Triangle is a cycle of three vertices, and that in particular it turns out that (ii) for every ($P_4+P_4$, Triangle)-free graph $G$ there is a family ${\cal S}$ of subsets of $V(G)$ inducing (complete) bipartite subgraphs of $G$, which contains polynomially many members and can be computed in polynomial time, such that every maximal independent set of $G$ is contained in some member of ${\cal S}$. These results seem to be harmonic with respect to other polynomial results for WIS on certain [subclasses of] $S_{i,j,k}$-free graphs and to other structure results on [subclasses of] Triangle-free graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Dominating Induced Matchings for $P_8$-free Graphs in Polynomial Time

Let $G=(V,E)$ be a finite undirected graph. An edge set $E' \subseteq E$ is a dominating induced matching (d.i.m.) in $G$ if every edge in $E$ is intersected by exactly one edge of $E'$. The Dominating Induced Matching (DIM) problem asks for the existence of a d.i.m. in $G$; this problem is also known as the Efficient Edge Domination problem. The DIM problem is related to parallel resource allocation problems, encoding theory and network routing. It is NP-complete even for very restricted graph classes such as planar bipartite graphs with maximum degree three and is solvable in linear time for $P_7$-free graphs. However, its complexity was open for $P_k$-free graphs for any $k \ge 8$; $P_k$ denotes the chordless path with $k$ vertices and $k-1$ edges. We show in this paper that the weighted DIM problem is solvable in polynomial time for $P_8$-free graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Maximum Weight Independent Set in lClaw-Free Graphs in Polynomial Time

The Maximum Weight Independent Set (MWIS) problem is a well-known NP-hard problem. For graphs $G_1, G_2$, $G_1+G_2$ denotes the disjoint union of $G_1$ and $G_2$, and for a constant $l \ge 2$, $lG$ denotes the disjoint union of $l$ copies of $G$. A {\em claw} has vertices $a,b,c,d$, and edges $ab,ac,ad$. MWIS can be solved for claw-free graphs in polynomial time; the first two polynomial time algorithms were introduced in 1980 by \cite{Minty1980,Sbihi1980}, then revisited by \cite{NakTam2001}, and recently improved by \cite{FaeOriSta2011,FaeOriSta2014}, and by \cite{NobSas2011,NobSas2015} with the best known time bound in \cite{NobSas2015}. Furthermore MWIS can be solved for the following extensions of claw-free graphs in polynomial time: fork-free graphs \cite{LozMil2008}, $K_2$+claw-free graphs \cite{LozMos2005}, and apple-free graphs \cite{BraLozMos2010,BraKleLozMos2008}. This manuscript shows that for any constant $l$, MWIS can be solved for $l$claw-free graphs in polynomial time. Our approach is based on Farber's approach showing that every $2K_2$-free graph has ${\cal O}(n^2)$ maximal independent sets \cite{Farbe1989}, which directly leads to a polynomial time algorithm for MWIS on $2K_2$-free graphs by dynamic programming. Solving MWIS for $l$claw-free graphs in polynomial time extends known results for claw-free graphs, for $lK_2$-free graphs for any constant $l$ \cite{Aleks1991,FarHujTuz1993,Prisn1995,TsuIdeAriShi1977}, for $K_2$+claw-free graphs, for $2P_3$-free graphs \cite{LozMos2012}, and solves the open questions for $2K_2+P_3$-free graphs and for $P_3$+claw-free graphs being two of the minimal graph classes, defined by forbidding one induced subgraph, for which the complexity of MWIS was an open problem.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Weighted Efficient Domination for $P_6$-Free Graphs in Polynomial Time

In a finite undirected graph $G=(V,E)$, a vertex $v \in V$ {\em dominates} itself and its neighbors in $G$. A vertex set $D \subseteq V$ is an {\em efficient dominating set} ({\em e.d.} for short) of $G$ if every $v \in V$ is dominated in $G$ by exactly one vertex of $D$. The {\em Efficient Domination} (ED) problem, which asks for the existence of an e.d. in $G$, is known to be NP-complete for $P_7$-free graphs but solvable in polynomial time for $P_5$-free graphs. The $P_6$-free case was the last open question for the complexity of ED on $F$-free graphs. Recently, Lokshtanov, Pilipczuk and van Leeuwen showed that weighted ED is solvable in polynomial time for $P_6$-free graphs, based on their sub-exponential algorithm for the Maximum Weight Independent Set problem for $P_6$-free graphs. Independently, at the same time, Mosca found a polynomial time algorithm for weighted ED on $P_6$-free graphs using a direct approach. In this paper, we describe the details of this approach which is simpler and much faster, namely its time bound is ${\cal O}(n^6 m)$.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

The stable set polytope of ($P_6$,triangle)-free graphs and new facet-inducing graphs

The stable set polytope of a graph $G$, denoted as STAB($G$), is the convex hull of all the incidence vectors of stable sets of $G$. To describe a linear system which defines STAB($G$) seems to be a difficult task in the general case. In this paper we present a complete description of the stable set polytope of ($P_6$,triangle)-free graphs (and more generally of ($P_6$,paw)-free graphs). For that we combine different tools, in the context of a well known result of Chvátal \cite{Chvatal1975} which allows to focus just on prime facet-inducing graphs, with particular reference to a structure result on prime ($P_6$,triangle)-free graphs due to Brandstädt et al. \cite{BraKleMah2005}. Also we point out some peculiarities of new facet-inducing graphs detected along this study with the help of a software.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Maximum Weight Independent Sets in Odd-Hole-Free Graphs Without Dart or Without Bull

The Maximum Weight Independent Set (MWIS) Problem on graphs with vertex weights asks for a set of pairwise nonadjacent vertices of maximum total weight. Being one of the most investigated and most important problems on graphs, it is well known to be NP-complete and hard to approximate. The complexity of MWIS is open for hole-free graphs (i.e., graphs without induced subgraphs isomorphic to a chordless cycle of length at least five). By applying clique separator decomposition as well as modular decomposition, we obtain polynomial time solutions of MWIS for odd-hole- and dart-free graphs as well as for odd-hole- and bull-free graphs (dart and bull have five vertices, say $a,b,c,d,e$, and dart has edges $ab,ac,ad,bd,cd,de$, while bull has edges $ab,bc,cd,be,ce$). If the graphs are hole-free instead of odd-hole-free then stronger structural results and better time bounds are obtained.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Dominating Induced Matchings for P7-Free Graphs in Linear Time

Let $G$ be a finite undirected graph with edge set $E$. An edge set $E' \subseteq E$ is an {\em induced matching} in $G$ if the pairwise distance of the edges of $E'$ in $G$ is at least two; $E'$ is {\em dominating} in $G$ if every edge $e \in E \setminus E'$ intersects some edge in $E'$. The \emph{Dominating Induced Matching Problem} (\emph{DIM}, for short) asks for the existence of an induced matching $E'$ which is also dominating in $G$; this problem is also known as the \emph{Efficient Edge Domination} Problem. The DIM problem is related to parallel resource allocation problems, encoding theory and network routing. It is \NP-complete even for very restricted graph classes such as planar bipartite graphs with maximum degree three. However, its complexity was open for $P_k$-free graphs for any $k \ge 5$; $P_k$ denotes a chordless path with $k$ vertices and $k-1$ edges. We show in this paper that the weighted DIM problem is solvable in linear time for $P_7$-free graphs in a robust way.

0 citations0 reviewsNo code linkedOpen access