On the Fixed-Parameter Tractability of the Equivalence Test of Monotone Normal Forms

Preprint series: 06-09, Reports on Computer Science

MSC:

Abstract: We examine the problem MONE---given
two irredundant, monotone formulas
$\varphi$ in DNF and $\psi$ in CNF,
decide whether they are
equivalent---in parameterized form.
We give fixed-parameter
algorithms for the following
parameters:

- the parameter number $k$ of
variables (thereby, we improve the
trivial $O(2^kn)$ time bound),
- number of monomials in $\varphi$
together with the size of a
largest monomial,
- a parameter describing the
frequencies of the variables
in $\varphi$ together with
the size of a largest monomial.

Our algorithms show that MONE is in
the class FPT for the respective
parameters.

Keywords: monotone normal form, equivalence, fixed-parameter tractability