Saarland University
Department of Computer Science
Computational Complexity
Computational Complexity




Computational Complexity - Bachelor's and Master's Theses

Mahmoud Fouz: Inapproximability of the Geometric Cover Polynomial

Master's Thesis, 2007.

Advisor: Prof. Dr. Markus Bläser

The geometric cover polynomial introduced by D'Antona and Munarini is a two-variable graph polynomial C(D; x, y) of a directed graph D. It counts, in a weighted sense, the number of decompositions of a directed graph into disjoint paths and cycles. It is the geometric version of the closely related cover polynomial introduced by Chung and Graham. Bläser and Dell have completely determined the complexity of exactly evaluating both polynomials. They show that these graph polynomials are #P-hard to evaluate at almost all points. We study the complexity of approximately evaluating the geometric cover polynomial. Under the reasonable complexity assumptions RP ≠ NP and RFP ≠ #P, we give a succinct characterization of a large class of points at which approximating the geometric cover polynomial within any polynomial factor is not possible.