PhD Course - Algebraic Graph Algorithms
Algebraic Graph Algorithms
Thore Husfeldt, ITU
Thore Husfeldt (ITU), Radu Curticapean (ITU), Andreas Björklund (Lund
Tuesdays, 14–16, starting Oct 16
Auditorium A at the Zoological Museum, Universitetsparken 15.
Algebraic Graph Algorithms is a Ph.D. course arranged by the center
for Basic Research in Algorithms (BARC), IT University of Copenhagen. The course aims
to give a comprehensive and from-scratch introduction to the algebraic graph algorithms,
covering early results that appear in disparate places (theoretical physics, combinatorics,
computer science), as well as recent advances in graph algorithms.
Classical Algorithms: Fisher–Kasteleyn–Temperley, Strassen, Freivalds’
fingerprinting, Lovasz-Edmonds, Ryser’s formula for the permanent, Kirchhoff’s matrix–
tree theorem, polynomial identity testing.
Graph polynomials (chromatic, Tutte), Ising and Potts model,
adjacency, incidence, and Tutte matrix of a graph, combinatorial interpretations of
Hafnian, determinant, permanent, fermionant, trace. Tree decompositions.
Möbius inversion, Holant-based algorithms, interpolation.
Reading list: The lecturers will produce lecture notes for each unit, week by week
Tentative at https://algebraicgraphalgorithms.wordpress.com
Very basic familiarity with graphs (in the combinatorial sense, i.e.,
sometimes called networks). Basic understanding of design and analysis of algorithms
(running times, algorithm, representation), including basic graph algorithms. (BFS,
Dijkstra, maybe some flow algorithm.) Linear algebra (independence, determinants) and
some abstract algebra (rings, fields, groups.) Basic discrete probability (random variables,
Weekly mandatory exercises, graded pass/fail. Mandatory lecture attendance
with active participation.
Amount of hours the student is expected to use on the course:
2h/w. Weekly exercises: 6,5h/2. Total 10 h/w. Expected total duration: 10
weeks. Total workload: 105 hours.
Ph.D. students in the greater Copenhagen area in relevant fields
(Algorithms, graph theory, theoretical physics), but with a core from the Basic Algorithms Research center (BARC).