Source author record

Andrea Munaro

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

ResearcherUnclaimed source record

Computational Geometry Discrete Mathematics Computational Complexity Data Structures and Algorithms math.CO

Catalog footprint

Research overview

3works

5topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Approximating Independent Set and Dominating Set on VPG graphs

We consider Independent Set and Dominating Set restricted to VPG graphs (or, equivalently, string graphs). We show that they both remain $\mathsf{NP}$ -hard on $B_0$ -VPG graphs admitting a representation such that each grid-edge belongs to at most one path and each horizontal path has length at most two. On the other hand, combining the well-known Baker's shifting technique with bounded mim-width arguments, we provide simple PTASes on VPG graphs admitting a representation such that each grid-edge belongs to at most $t$ paths and the length of the horizontal part of each path is at most $c$ , for some $c \geq 1$ .

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.

preprint2016arXiv

The VC-Dimension of Graphs with Respect to k-Connected Subgraphs

We study the VC-dimension of the set system on the vertex set of some graph which is induced by the family of its $k$ -connected subgraphs. In particular, we give tight upper and lower bounds for the VC-dimension. Moreover, we show that computing the VC-dimension is $\mathsf{NP}$ -complete and that it remains $\mathsf{NP}$ -complete for split graphs and for some subclasses of planar bipartite graphs in the cases $k = 1$ and $k = 2$ . On the positive side, we observe it can be decided in linear time for graphs of bounded clique-width.

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.