TY  - THES
T1  - Computational complexity of graph polynomials
A1  - Hoffmann,Christian
Y1  - 2011/06/28
N2  - 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.
KW  -  Chromatisches Polynom
KW  - Reduktionssystem
KW  - Algorithmus
CY  - Saarbrücken
PB  - Universitäts- und Landesbibliothek
AD  - Postfach 151141, 66041 Saarbrücken
UR  - http://scidok.sulb.uni-saarland.de/volltexte/2011/3681
ER  -