Source author record

Irene Muzi

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

ResearcherUnclaimed source record

Data Structures and Algorithms math.CO Discrete Mathematics Information Theory math.IT

Catalog footprint

Research overview

3works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Harmless Sets in Sparse Classes

In the classic TARGET SAT SELECTION problem, we are asked to minimise the number of nodes to activate so that, after the application of a certain propagation process, all nodes of the graph are active. Bazgan and Chopin [Discrete Optimization}, 14:170--182, 2014] introduced the opposite problem, named HARMLESS SET, in which they ask to maximise the number of nodes to activate such that not a single additional node is activated. In this paper we investigate how sparsity impacts the tractability of HARMLESS SET. Specifically, we answer two open questions posed by the aforementioned authors, namely a) whether the problem is FPT on planar graphs and b) whether it is FPT parametrised by treewidth. The first question can be answered in the positive using existing meta-theorems on sparse classes, and we further show that HARMLESS SET not only admits a polynomial kernel, but that it can be solved in subexponential time. We then answer the second question in the negative by showing that the problem is W[1]-hard when parametrised by a parameter that upper bounds treewidth.

preprint2016arXiv

Half-integral linkages in highly connected directed graphs

We study the half-integral $k$ -Directed Disjoint Paths Problem ( $\tfrac12$ kDDPP) in highly strongly connected digraphs. The integral kDDPP is NP-complete even when restricted to instances where $k=2$ , and the input graph is $L$ -strongly connected, for any $L\geq 1$ . We show that when the integrality condition is relaxed to allow each vertex to be used in two paths, the problem becomes efficiently solvable in highly connected digraphs (even with $k$ as part of the input). Specifically, we show that there is an absolute constant $c$ such that for each $k\geq 2$ there exists $L(k)$ such that $\tfrac12$ kDDPP is solvable in time $O(|V(G)|^c)$ for a $L(k)$ -strongly connected directed graph $G$ . As the function $L(k)$ grows rather quickly, we also show that $\tfrac12$ kDDPP is solvable in time $O(|V(G)|^{f(k)})$ in $(36k^3+2k)$ -strongly connected directed graphs. We also show that for each $ε<1$ deciding half-integral feasibility of kDDPP instances is NP-complete when $k$ is given as part of the input, even when restricted to graphs with strong connectivity $εk$ .

preprint2012arXiv

Degree-doubling graph families

Let G be a family of n-vertex graphs of uniform degree 2 with the property that the union of any two member graphs has degree four. We determine the leading term in the asymptotics of the largest cardinality of such a family. Several analogous problems are discussed.

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.