טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
Ph.D Thesis
Ph.D StudentAverbouch Ilia
SubjectCompleteness and Universality Properties of Graph
Invariants and Graph Polynomials
DepartmentDepartment of Computer Science
Supervisor Professor Emeritus Johann Makowsky
Full Thesis textFull thesis text - English Version


Abstract

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.