Advanced Topics in Computer Science (238901)

Spring semester 2010
last updated: 09.03.2010

Graph polynomials and their Complexity

NEW (1.3.2010): List of topics for seminar talks.

NEW (1.3.2010): Slides of given lectures

For those graduate students who have already taken 238901 before,
but on another topic, arrangements will be found to get credit again.

Lecturer: Prof. J.A. Makowsky and participants
NEW TIME: Sunday, 10:30-12:30
New Place: Taub 601

Prerequisites: Computability, some elementary graph theory,
some familiarity with linear and abstract algebra.
Format: Two hours frontal presentations.
Requirements: Edited version of frontal presentation or final project.

Outline

A common generalization of counting problems are graph polynomials. The most prominent of these are the matching polynomials, the colouring polynomials and the Tutte polynomial. For general graphs these are often hard to compute (#P hard). There are also various multivariate generalizations of these polynomials.
  1. A catalogue of prominent graph polynomials.
    Slides on prominent polynomials from 238900-2006:
    http://www.cs.technion.ac.il/~janos/COURSES/238900/slides.html
    ISF funded research project on Graph Polynomials:
    http://www.cs.technion.ac.il/~janos/RESEARCH/gp-homepage.html
  2. Distinctive power of graph polynomials
  3. Reducibilities between graph polynomials
  4. Easy and difficult evaluations of graph polynomials
  5. Towards an algebraic complexity theory