Seminar: Graph Homomorphisms

• Course codes: B-AUK-S→KTH-BS ·M-AuK-S→KTH-MS
• External links: qis

Description

This seminar explores the rich connection between the number of induced subgraphs, not necessarily induced subgraphs, graph homomorphisms, and other graph parameters. We will discuss elegant combinatorics, efficient algorithms, and hardness results. The focus will be on algorithms and complexity of problems related to finding and counting homomorphisms between graphs.

Teachers

• Holger Dell
• Anselm Haak
• Leo Krull

Schedule

Weekly 2-hour sessions during the semester.

In the beginning, we will read Chapters 1-5 of Large networks and graph limits by Lázló Lovász together, with each participant giving a short talk on part of it. Subsequently, each participant will present an advanced topic from the area based on one of the papers listed below in a longer talk and in a short written report.

A detailed schedule will follow later.

Literature

• Lovász (2012): Large networks and graph limits.
  The standard book on the topic, focuses on the combinatorics.

• Curticapean, Dell, Marx (2017): Homomorphisms Are a Good Basis for Counting Small Subgraphs.
  The most efficient known general algorithms for counting small subgraphs.

• Marx (2010): Can you beat treewidth?.
  Conditional lower bound for Decision-Hom(G,H) based on the structure of G.

• Hell, Nesětřil (1990): On the Complexity of H-Coloring.
  Complexity of Decision-Hom(G,H) for small H.

• Dyer, Greenhill (2000): The Complexity of Counting Graph Homomorphisms.
  Complexity of #Hom(G,H) for small H.

• Grohe (2007): The Complexity of Homomorphism and Constraint Satisfaction Problems Seen from the Other Side.
  Complexity classification for Decision-Hom(G,H) based on the structure of H.

• Dalmau, Johnson (2004): The complexity of counting homomorphisms seen from the other side.
  Complexity classification for #Hom(G,H) based on the structure of H.

• Bulatov, Kazeminia (2022): Complexity classification of counting graph homomorphisms modulo a prime number.
  Complexity classification for #Hom(G,H) modulo a prime number based on the structure of H.

• Bulatov, Dalmau, Grohe, Marx (2012): Enumerating Homomorphisms.
  Study of the problem of enumerating all homomorphisms between to graphs.

Lernziele

Nach dem Seminar kann der:die Student:in:

• Wissenschaftlichen Vorträgen aktiv zuhören und sich an Diskussionen beteiligen,
• Fachliteratur auf fortgeschrittenem Forschungsniveau eigenständig lesen und dabei Verständnisfragen identifizieren,
• wissenschaftliche Inhalte auf didaktisch geeignete Weise in einem Vortrag vermitteln und reflektiert einordnen,
• Forschungsinhalte den wissenschaftlichen Konventionen folgend schriftlich darstellen und reflektiert einordnen,
• didaktische Aspekte eines Vortrags und eines wissenschaftlichen Schriftstücks bewerten und diskutieren.

Formale Anforderungen

Um das Seminar zu bestehen, werden folgende Aktivitäten erwartet:

• Einen kurzen (~15 Minuten) Vortrag über einführende Grundlagen (Abschnitt(e) aus Large networks and graph limits) halten,
• einen längeren (~40 Minuten) Vortrag über ein fortgeschrittenes Thema halten (zum Beispiel eines der oben genannten Paper),
• sich aktiv an der Diskussion beteiligen,
• eigenständig offene Fragen identifizieren und das Lehrpersonal vor dem Vortrag hierzu befragen,
• 7 Tage vor jedem Vortrag: einen Entwurf der Folien oder des geplanten Tafelanschriebs an das Lehrpersonal senden. Darauf erhalten Sie dann in einem persönlichen Gespräch Feedback, das Sie in den Vortrag einarbeiten.
• 7 Tage nach dem langen Vortrag: eine Ausarbeitung (ca.\ zwei Seiten) an zwei andere Studierende senden. Der Vortrag fasst das Material in eigenen Worten zusammen, nennt Referenzen, und stellt Zusammenhänge zu anderen Themen des Buchs her.
• 14 Tage nach dem langen Vortrag: Sie erhalten Feedback von den anderen Studierenden,
• 21 Tage nach dem langen Vortrag: die endgültige Version der Ausarbeitung zur Bewertung an das Lehrpersonal senden.

Bewertung

Nach jedem Vortrag gibt es eine offene Feedbackrunde im Plenum und eine geschlossene Feedbackrunde im Einzelgespräch. Die vorläufige Benotung erfolgt direkt nach dem Vortrag. Bewertet werden:

• Inwiefern haben Sie inhaltliche Fragen vor dem Vortrag geklärt?
• Wie haben Sie sich an die zeitliche Vorgabe gehalten?
• Wie effektiv haben Sie während des Vortrags Fragen beantwortet?
• Wie intensiv haben Sie sich an Diskussionen beteiligt? (hierbei zählen sowohl aktive Fragen als auch hilfreiche Antworten)
• Wie gut haben Sie die Inhalte des Vortrags selbst durchdrungen?
• Wie nützlich waren die im Vortrag gezeigten Visualisierungen?
• Wie verständlich konnten Sie die Inhalte des Vortrags an die anderen Studierenden vermitteln?
• Wie unterhaltsam war Ihr Vortrag?
• Je kürzer oder einfacher das Paper ist, desto mehr Wert wird auf den Vortragsstil, das selbstständige Arbeiten, die Darstellung der umliegenden Literatur, und die Motivation gelegt (also z.B. warum ist das Paper interessant und auf welche Forschungsfragen hat das Ergebnis einen Einfluss?). Alternativ können Sie auch zwei kurze Paper bearbeiten.

Allgemeine Tipps

• Zeit für die Vorbereitung. Lesen kann sehr viel Zeit in Anspruch nehmen. Fangen Sie so früh wie möglich an.
• Nicht verzweifeln. Es ist ganz natürlich, dass Sie die Hälfte der Begriffe nicht verstehen werden. Das geht uns oft genauso. Gehen Sie systematisch Begriff für Begriff vor, und klären Sie für jeden einzelnen Begriff, was er bedeutet. Schreiben Sie sich auf, was sie gelernt haben.
• Zeit für den Vortrag. Die vorgegebene Zeit geht viel schneller vorbei, als Sie zunächst denken. Eine gute Faustregel ist, mit 1-2 Minuten pro Folie zu planen.

• Stellen Sie Fragen. Nichts ist langweiliger, als ein Vortrag, bei dem Sie auf Folie 2 die Definition eines Hinzlipunzli nicht verstanden haben, weil der Vortragende darüber etwas zu schnell hinwegging. Übernehmen Sie Verantwortung und fragen Sie aktiv! Unwissenheit ist keine Peinlichkeit, sondern eine spannende Gelegenheit, etwas zu lernen.
• Seien Sie ehrlich. Es wird nicht erwartet, dass Sie alles wissen oder jede Frage beantworten können. Wenn Sie verwirrt sind, etwas nicht verstehen, oder einen Teil des Inhalts aus Zeitgründen nicht detailliert lesen konnten, stehen Sie dazu. Das ist wissenschaftliches Arbeiten.
• Seien Sie witzig. Bauen Sie einen Witz oder einen Spaß in den Vortrag ein (aber auf keinen Fall mehr als zwei Witze).
• Weniger ist mehr. Gehen Sie lieber bei wenigen Unterthemen in die Tiefe, als alles nur halbgar und halbverständlich anzureißen.