Source author record

Raffaele Mosca

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

ResearcherUnclaimed source record

Discrete Mathematics math.CO Computer Science and Game Theory econ.GN q-fin.EC

Catalog footprint

Research overview

14works

5topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

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.

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.

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.

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.

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.

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.

preprint2016arXiv

Bounded Clique-Width of ( $S_{1,2,2}$ ,Triangle)-Free Graphs

If a graph has no induced subgraph isomorphic to $H_1$ or $H_2$ then it is said to be ( $H_1,H_2$ )-free. Dabrowski and Paulusma found 13 open cases for the question whether the clique-width of ( $H_1,H_2$ )-free graphs is bounded. One of them is the class of ( $S_{1,2,2}$ ,triangle)-free graphs. In this paper we show that these graphs have bounded clique-width. Thus, also ( $P_1+2P_2$ ,triangle)-free graphs have bounded clique-width which solves another open problem of Dabrowski and Paulusma. Meanwhile we were informed by Paulusma that in December 2015, Dabrowski, Dross and Paulusma showed that ( $S_{1,2,2}$ ,triangle)-free graphs (and some other graph classes) have bounded clique-width.

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.

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.

preprint2016arXiv

Maximum Weight Independent Sets for ( $P_7$ ,Triangle)-Free Graphs in Polynomial Time

The Maximum Weight Independent Set (MWIS) problem on finite undirected graphs with vertex weights asks for a set of pairwise nonadjacent vertices of maximum weight sum. MWIS is one of the most investigated and most important algorithmic graph problems; it is well known to be NP-complete, and it remains NP-complete even under various strong restrictions such as for triangle-free graphs. Its complexity was an open problem for $P_k$ -free graphs, $k \ge 5$ . Recently, Lokshtanov, Vatshelle, and Villanger proved that MWIS can be solved in polynomial time for $P_5$ -free graphs, and Lokshtanov, Pilipczuk, and van Leeuwen proved that MWIS can be solved in quasi-polynomial time for $P_6$ -free graphs. It still remains an open problem whether MWIS can be solved in polynomial time for $P_k$ -free graphs, $k \geq 6$ or in quasi-polynomial time for $P_k$ -free graphs, $k \geq 7$ . Some characterizations of $P_k$ -free graphs and some progress are known in the literature but so far did not solve the problem. In this paper, we show that MWIS can be solved in polynomial time for ( $P_7$ ,triangle)-free graphs. This extends the corresponding result for ( $P_6$ ,triangle)-free graphs and may provide some progress in the study of MWIS for $P_7$ -free graphs.

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

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.

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.

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.

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.

Raffaele Mosca

Research overview

Is this your work?

14 publications

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

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

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

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

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

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

Bounded Clique-Width of ( $S_{1,2,2}$ ,Triangle)-Free Graphs

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

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

Maximum Weight Independent Sets for ( $P_7$ ,Triangle)-Free Graphs in Polynomial Time

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

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

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

Dominating Induced Matchings for P7-Free Graphs in Linear Time

See the researcher in context

Building this map preview

Raffaele Mosca

Research overview

Is this your work?

14 publications

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

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

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

Finding Dominating Induced Matchings in P9P_9P9​-Free Graphs in Polynomial Time

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

Independent sets in (P4+P4P_4+P_4P4​+P4​,Triangle)-free graphs

Bounded Clique-Width of (S1,2,2S_{1,2,2}S1,2,2​,Triangle)-Free Graphs

Dominating Induced Matchings for P8P_8P8​-free Graphs in Polynomial Time

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

Maximum Weight Independent Sets for (P7P_7P7​,Triangle)-Free Graphs in Polynomial Time

Weighted Efficient Domination for P6P_6P6​-Free Graphs in Polynomial Time

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

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

Dominating Induced Matchings for P7-Free Graphs in Linear Time

See the researcher in context

Building this map preview

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

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

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

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

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

Bounded Clique-Width of ( $S_{1,2,2}$ ,Triangle)-Free Graphs

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

Maximum Weight Independent Sets for ( $P_7$ ,Triangle)-Free Graphs in Polynomial Time

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

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