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.