"Algorithmic and Computational Complexity Issues of MONET

Vorschau

Inhaltsverzeichnis, Datei (48 KB)
Leseprobe, Datei (120 KB)

In this thesis, we study the problem Monet—the Mo(notone) n(ormal form)
e(quivalence) t(est)—that asks to decide equivalence of a monotone disjunctive normal form . and a monotone conjunctive normal form ψ. This problem is a covering problem that can be interpreted as the task of enumerating all (in some sense) minimal solutions of some system. Hence, there is a huge number of similar questions in many problems from diverse applications.Our results can roughly be divided into results on the design and evaluation of algorithms for Monet and results that rather touch complexity questions related to the problem. As for the algorithmic part, we will give lower bounds for several known algorithms and report results obtained by practically examining the theoretically
fastest algorithm in computational experiments. As for the complexity
part of this thesis, we show several restricted classes of the problem to be solvable in logarithmic space, which improves previously known polynomial time bounds. We also show Monet to be in the complexity class of .xed-arameter tractable problems with respect to several parameters. More precisely, we prove the following main results using various algorithmic and computational complexity techniques. – Several restricted classes of Monet are solvable in logarithmic space. In
particular, these are the classes where the DNF– contains only a constant number of monomials (Section 4.1.1), contains only monomials of constant size (Section 4.1.2), contains only monomials that each do not contain only a constant number of variables
(Section 4.1.3),- is regular (Section 4.2.1), aligned (Section 4.2.2), or 2-monotonic (Section 4.2.3).- The DL-algorithm (Section 5.1.2), the BMR-algorithm (Section 5.1.3), the KS-algorithm (Section 5.1.4), and the HBC-algorithm (Section 5.2) for the
problem Monet are not output-polynomial. Their running times are at
least nÙ(log log n), where n denotes the size of the input and output.-FK-algorithm B for the problem Monet is experimentally competitive to FK-algorithm A on many classes (Chapter 6).-Monet is .xed-parameter tractable with respect to the parameters
– number v of variables in . and ψ (Section 7.1),
– number m of monomials in . (Section 7.2),
– a parameter q describing the variable frequencies in . (Section 7.3),
– and a parameter bounding the unions of transversals or edges of .’s
associated hypergraph (Section 7.4.3).
This thesis contains material (to be) published in the journals Discrete Applied Mathematics, Information and Computation and Information Processing Letters, as well as material (to be) presented at, and (to be) published in the proceedings
of, the conference “Mathematical Foundations of Computer Science” (MFCS 2005), and the workshops “Graph-Theoretic Concepts in Computer Science” (WG 2007), “Parameterized and Exact Computation” (IWPEC 2008) and “Workshop on Algorithm Engineering & Experiments” (ALENEX 2009).