Campus Event Calendar
Event Entry
What and Who
The Geometric Cover Polynomial - Hardness and Inapproximability
Mahmoud Fouz
Talk
AG 1, AG 2, AG 3, AG 4, AG 5, SWS, RG1, RG2
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Monday, 25 February 2008
09:00
330 Minutes
E1 4
024
Saarbrücken
Abstract
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 almost completely determined the complexity of
\emph{exactly} evaluating both polynomials. They show that these graph
polynomials are $\#P$-hard to evaluate at almost all points. Im my
Master's thesis, I studied the complexity of \textit{approximately}
evaluating the (geometric) cover polynomial. Under some reasonable
complexity assumptions, 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.
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 almost completely determined the complexity of
\emph{exactly} evaluating both polynomials. They show that these graph
polynomials are $\#P$-hard to evaluate at almost all points. Im my
Master's thesis, I studied the complexity of \textit{approximately}
evaluating the (geometric) cover polynomial. Under some reasonable
complexity assumptions, 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.
Contact
imprs
225
--email hidden
passcode not visible
logged in users only
Jennifer Gerling, 02/22/2008 17:17 -- Created document.