SciDok

Eingang zum Volltext in SciDok

Lizenz

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


Computational complexity of graph polynomials

Hoffmann, Christian

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

Bookmark bei Connotea Bookmark bei del.icio.us
SWD-Schlagwörter: Chromatisches Polynom , Reduktionssystem , Algorithmus
Freie Schlagwörter (Deutsch): Graphpolynom , Interlacepolynom
Freie Schlagwörter (Englisch): algorithm , graph polynomial , chromatic polynomial
Institut: Fachrichtung 6.2 - Informatik
Fakultät: Fakultät 6 - Naturwissenschaftlich-Technische Fakultät I
DDC-Sachgruppe: Informatik
Dokumentart: Dissertation
Hauptberichter: Bläser, Markus (Prof. Dr.)
Sprache: Englisch
Tag der mündlichen Prüfung: 20.08.2010
Erstellungsjahr: 2010
Publikationsdatum: 28.06.2011
Kurzfassung auf Englisch: The thesis provides hardness and algorithmic results for graph polynomials. We observe VNP-completeness of the interlace polynomial, and we prove VNP-completeness of almost all q-restrictions of Z(G; q; x), the multivariate Tutte polynomial. Using graph transformations, we obtain point-to-point reductions for graph polynomials.We develop two general methods: Vertex/edge cloning and, more general,uniform local graph transformations. These methods unify known and new hardness-of-evaluation results for graph polynomials. We apply both methods to several examples. We show that, almost everywhere, it is #P-hard to evaluate the two-variable interlace polynomial and the (normal as well as extended) bivariate chromatic polynomial. Almost everywhere" means that the dimension of the set of exceptional points is strictly less than the dimension of the domain of the graph polynomial. We also give an inapproximability result for evaluation of the independent set polynomial. Providing a new family of reductions for the interlace polynomial that increases the instance size only polylogarithmically, we obtain an exp(Ω (n= log3 n)) time lower bound for evaluation of the independent set polynomial under a counting version of the exponential time hypothesis. We observe that the extended bivariate chromatic polynomial can be computed in vertex-exponential time. We devise a means to compute the interlace polynomial using tree decompositions. This enables a parameterized algorithm to evaluate the interlace polynomial in time linear in the size of the graph and single-exponential in the treewidth. We give several versions of the algorithm, including a parallel one and a faster way to compute the interlace polynomial of any graph. Finally, we propose two faster algorithms to compute/evaluate the interlace polynomial in special cases.
Kurzfassung auf Deutsch: Diese Arbeit beinhaltet Härteresultate und Algorithmen für Graphpolynome. Wir stellen zunächst fest, dass das Interlacepolynom VNP-vollständig ist, und wir zeigen die VNP-Vollständigkeit fast aller q-Restriktionen des multivariaten Tutte-Polynoms Z(G; q; x). Unter Verwendung von Graphtransformationen erhalten wir Punkt-zu-Punkt-Reduktionen für Graphpolynome. Dabei entwickeln wir auch zwei allgemeine Methoden: Das Klonen von Knoten bzw. Kanten und, allgemeiner, uniforme lokale Graphtransformationen. Beide Methoden vereinheitlichen bekannte und neue Härteresultate für das Auswerten von Graphpolynomen. Wir wenden beide Methoden auf verschiedene Beispiele an. Wir zeigen, dass es fast überall #P-schwer ist, das Interlacepolynom in zwei Variablen bzw. das (normale oder erweiterte) bivariatechromatische Polynom auszuwerten. Fast überall heißt hier: Überall, außerauf einer Ausnahmemenge, deren Dimension um mindestens eins kleiner ist als der Definitionsbereich des Graphpolynoms. Wir zeigen auch, dass näherungsweises Auswerten des Independent-Set-Polynoms schwer ist. Wir entwickeln eine neue Familie von Reduktionen für das Interlacepolynom, die die Instanz nur polylogarithmisch vergrößert. Damit zeigen wir, unter Annahme einer Variante der Exponentialzeit-Hypothese, dass das Auswerten des Independent-Set-Polynoms fast überall Zeit exp(Ω(n= log3 n)) benötigt. Wir stellen fest, dass das erweiterte bivariate chromatische Polynom in Zeit exponentiell in der Knotenzahl berechnet werden kann. Wir entwickeln ein Mittel, um das Interlacepolynom mit Hilfe von Baumzerlegungen zu berechnen. Das führt zu einem parametrisierten Algorithmus zum Auswerten des Interlacepolynoms mit Laufzeit linear in der Anzahl der Knoten und einfach exponentiell in der Weite der gegebenen Baumzerlegung. Wir diskutieren verschiedene Varianten dieses Algorithmus, einschließlich Parallelisierung und einer Möglichkeit, das Interlacepolynom jedes Graphen asymptotisch schneller zu berechnen. Schließlich geben wir zwei schnellere Algorithmen an, die das Interlacepolynomin speziellen Situationen berechnen.
Lizenz: Standard-Veröffentlichungsvertrag

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