Ph.D Thesis | |

Ph.D Student | Averbouch Ilia |
---|---|

Subject | Completeness and Universality Properties of Graph Invariants and Graph Polynomials |

Department | Department of Computer Science |

Supervisor | PROFESSOR EMERITUS Johann Makowsky |

Full Thesis text |

Graph
polynomials are powerful and well-developed tools to express graph parameters.
Usually graph polynomials are compared to each other by ad-hoc means allowing
to decide whether a newly defined graph polynomial generalizes (or is
generalized by) another one. We study their distinctive power and introduce the
notions of *dp-completeness* and *universality* of graph polynomials
in order to formalize dependencies between them.

Many known graph polynomials satisfy linear recurrence relations with respect to some set of edge- or vertex-elimination operations. Inspired by the work of Brylawski and Oxley on the Tutte polynomial, we define several classes of graph polynomials according to their recurrence relations and prove dp-completeness and universality results for these classes. We also extend our results to classes of labeled graph polynomials.

We provide several observations regarding computational complexity of the discussed dp-complete graph polynomials. Notably, we exploit definability properties of these polynomials to show that they can be computed efficiently when input graphs are limited by a certain parameter and present some explicit algorithms.