Source author record

G. Muciaccia

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

ResearcherUnclaimed source record

Computational Complexity Data Structures and Algorithms

Catalog footprint

Research overview

2works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2013arXiv

Maximum Balanced Subgraph Problem Parameterized Above Lower Bound

We consider graphs without loops or parallel edges in which every edge is assigned + or -. Such a signed graph is balanced if its vertex set can be partitioned into parts $V_1$ and $V_2$ such that all edges between vertices in the same part have sign + and all edges between vertices of different parts have sign $-$ (one of the parts may be empty). It is well-known that every connected signed graph with $n$ vertices and $m$ edges has a balanced subgraph with at least $\frac{m}{2} + \frac{n-1}{4}$ edges and this bound is tight. We consider the following parameterized problem: given a connected signed graph $G$ with $n$ vertices and $m$ edges, decide whether $G$ has a balanced subgraph with at least $\frac{m}{2} + \frac{n-1}{4}+\frac{k}{4}$ edges, where $k$ is the parameter. We obtain an algorithm for the problem of runtime $8^k(kn)^{O(1)}$ . We also prove that for each instance $(G,k)$ of the problem, in polynomial time, we can either solve $(G,k)$ or produce an equivalent instance $(G',k')$ such that $k'\le k$ and $|V(G')|=O(k^3)$ . Our first result generalizes a result of Crowston, Jones and Mnich (ICALP 2012) on the corresponding parameterization of Max Cut (when every edge of $G$ has sign $-$ ). Our second result generalizes and significantly improves the corresponding result of Crowston, Jones and Mnich: they showed that $|V(G')|=O(k^5)$ .

preprint2012arXiv

(Non-)existence of Polynomial Kernels for the Test Cover Problem

The input of the Test Cover problem consists of a set $V$ of vertices, and a collection ${\cal E}=\{E_1,..., E_m\}$ of distinct subsets of $V$ , called tests. A test $E_q$ separates a pair $v_i,v_j$ of vertices if $|\{v_i,v_j\}\cap E_q|=1.$ A subcollection ${\cal T}\subseteq {\cal E}$ is a test cover if each pair $v_i,v_j$ of distinct vertices is separated by a test in ${\cal T}$ . The objective is to find a test cover of minimum cardinality, if one exists. This problem is NP-hard. We consider two parameterizations the Test Cover problem with parameter $k$ : (a) decide whether there is a test cover with at most $k$ tests, (b) decide whether there is a test cover with at most $|V|-k$ tests. Both parameterizations are known to be fixed-parameter tractable. We prove that none have a polynomial size kernel unless $NP\subseteq coNP/poly$ . Our proofs use the cross-composition method recently introduced by Bodlaender et al. (2011) and parametric duality introduced by Chen et al. (2005). The result for the parameterization (a) was an open problem (private communications with Henning Fernau and Jiong Guo, Jan.-Feb. 2012). We also show that the parameterization (a) admits a polynomial size kernel if the size of each test is upper-bounded by a constant.

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.