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

by    Matthias Hagen

Preprint series: 06-09, Reports on Computer Science

MSC:
68Q25 Analysis of algorithms and problem complexity [See also 68W40]

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

Upload: 2006-06-29

Update: 2006 -06 -29


The author(s) agree, that this abstract may be stored as full text and distributed as such by abstracting services.