SciDok

Eingang zum Volltext in SciDok

Lizenz

Dissertation zugänglich unter
URN: urn:nbn:de:bsz:291-scidok-44713
URL: http://scidok.sulb.uni-saarland.de/volltexte/2011/4471/


Polynomially solvable cases of hypergraph transversal and related problems

Polynomialzeitlösbare Klassen des Transversalhypergraphen-Problems und verwandte Probleme

Rauf, Imran

pdf-Format:
Dokument 1.pdf (656 KB)

Bookmark bei Connotea Bookmark bei del.icio.us
SWD-Schlagwörter: Graph , Effizienter Algorithmus , Algorithmus , Boolesche Funktion
Freie Schlagwörter (Deutsch): Transversalhypergraphen-Problem , monotone boolesche funktion , Mengensystem
Freie Schlagwörter (Englisch): hypergraph transversal problem , enumeration algorithms , output polynomial time algorithm
CCS - Klassifikation: Computatio , Graphs and
Institut: Fachrichtung 6.2 - Informatik
Fakultät: Fakultät 6 - Naturwissenschaftlich-Technische Fakultät I
DDC-Sachgruppe: Informatik
Dokumentart: Dissertation
Hauptberichter: Mehlhorn, Kurt (Prof. Dr. Dr. h.c. mult.)
Sprache: Englisch
Tag der mündlichen Prüfung: 25.10.2011
Erstellungsjahr: 2011
Publikationsdatum: 01.12.2011
Kurzfassung auf Englisch: This thesis is mainly concerned with the hypergraph transversal problem, which asks to generate all minimal transversals of a given hypergraph. While the current best upper bound on the complexity of the problem is quasi-polynomial in the combined input and output sizes, it is shown to be solvable in output polynomial time for a number of hypergraph classes. We extend this polynomial frontier to the hypergraphs induced by hyperplanes and constant-sided polytopes in fixed dimension R^d and hypergraphs for which every minimal transversal and hyperedge intersection is bounded. We also show the problem to be fixed parameter tractable with respect to the minimum integer k such that the input hypergraph is k-degenerate, and also with respect to its maximum complementary degree. Whereas we improve the known bounds when the parameter is the maximum degree of a hypergraph. We also study the readability of a monotone Boolean function which is defined as the minimum integer r such that it can be represented by an AND-OR-formula with every variable occurrence is bounded by r. We prove that it is NP-hard to approximate the readability of even a depth three Boolean formula. We also give tight sublinear upper bounds on the readability of a monotone Boolean function given in CNF (or DNF) form, parameterized by the number of terms in the CNF and the maximum number of variables in the intersection of any constant number of terms. For interval DNF's we give much tighter logarithmic bounds on the readability. Finally, we discuss an implementation of a quasi-polynomial algorithm for the hypergraph transversal problem that runs in polynomial space. We found our implementation to be competitive with all but one previous implementation on various datasets.
Kurzfassung auf Deutsch: Diese Dissertation behandelt hauptsächlich das Transversalhypergraphen-Problem: gegeben ein Hypergraph, generiere alle seine minimalen Transversalen. Obwohl die bisher beste obere Schranke für die Komplexität dieses Problems quasi-polynomiell in der Größe der Ein- und Ausgabe ist, sind für viele Klassen von Hypergraphen output-polynomielle Lösungen bekannt. Wir zeigen für zwei weitere Klassen von Hypergraphen, dass sie output-polynomielle Lösungen besitzen. Zum einen sind dies Hypergraphen, die durch Hyperebenen und Polytope mit konstanter Seitenzahl im R^d für eine feste Dimension d induziert werden; zum anderen sind dies Hypergraphen, für die die Größe der Schnittmenge jedes Transversalen und jeder Hyperkante beschränkt ist. Desweiteren zeigen wir, dass das Problem fixed-parameter tractable ist, wenn als Parameter der maximale inverse Knotengrad des eingegebenen Hypergraphen gewählt wird oder der Parameter k die kleinste natürliche Zahl ist, für die der eingegebene Hypergraph k-degeneriert ist. Wir verbessern die bekannten fixed-parameter Ergebnisse für den Parameter des maximalen Knotengrads des eingegebenen Hypergraphen. Außerdem untersuchen wir die readability von monotonen Booleschen Funktionen. Diese ist als kleinste natürliche Zahl r definiert, so dass die Funktion als AND-OR-Formel repräsentiert werden kann, in der jede Variable höchstens r-mal vorkommt. Wir beweisen, dass die Approximation der readability schon für Boolesche Formeln der Tiefe 3 NP-hart ist. Darüberhinaus geben wir scharfe sublineare untere Schranken für die readability monotoner Boolescher Funktionen an, die in KNF-Form (oder DNF-Form) gegeben sind, wenn über die Anzahl der Terme der KNF und die maximale Anzahl an Variablen im Durchschnitt einer konstanten Anzahl von Termen parametrisiert wird. Für intervall-DNF geben wir noch schärfere logarithmische Schranken für die readability an. Schließlich behandeln wir für das Transversalhypergraphen-Problem noch die Implementation eines quasi-polynomiellen Algorithmus, der mit polynomiellen Platzbedarf auskommt. Auf verschiedenen Datensätzen ist unsere Implementation zu allen vorherigen Implementationen (außer einer) konkurrenzfähig.
Lizenz: Veröffentlichungsvertrag für Dissertationen und Habilitationen

Home | Impressum | Über SciDok | Policy | Kontakt | Datenschutzerklärung | English