Parametrisierte Algorithmen auf Graphen

Algorithmen sind ein komplexes und vielseitiges Thema mit vielen Anwendungen im realen Leben. Wir haben uns im Rahmen der PACE-Challenge (Parameterized Algorithms and Computational Experiments) mit dem Problem des Cluster-Editings auseinandergesetzt.

Die PACE-Challenge wurde 2015 ins Leben gerufen, um die Beziehung zwischen der Theorie der parametrisierten Algorithmen und der Praxis zu vertiefen. Ziel ist es, ein vorgegebenes Problem möglichst schnell zu lösen. Die PACE-Challenge hat sich zusätzlich zum Ziel gesetzt, das Voranbringen von neuen theoretischen Ansätzen zu fördern, sowie die Konkurrenzfähigkeit von Algorithmen in der Praxis zu untersuchen.

Natürlich wäre es großartig, die Challenge zu gewinnen, aber das ist nicht die Hauptmotivation des Projekts. Unser Ziel ist vor allem das Erlangen neuer Kompetenzen zur Lösung komplexer Probleme und der Spaß am Projekt.

Wie schon erwähnt, ist das diesjährige Thema der PACE-Challenge das Problem des Cluster-Editings. Beim Cluster-Editing soll ein Graph durch eine minimale Zahl an Kantenmodifikationen in disjunkte Cliquen (vollständige Teilgraphen) überführt werden. Ein Anwendungsbeispiel: wir möchten eine Menge von Studierenden in Lerngruppen aufteilen. Wir modellieren Studierende durch Knoten eines Graphen und verbinden zwei Studierende durch eine Kante, wenn sie zusammen arbeiten möchten. Knoten, die nicht verbunden sind, repräsentieren Studierende, die nicht zusammenarbeiten möchten. Die Lösung einer solchen Cluster-Editing-Instanz liefert uns eine Menge von Lerngruppen von Studierenden, sodass möglichst wenige Wünsche missachtet werden. Das Cluster-Editing Problem gilt in der klassischen Komplexitätstheorie als nicht effizient lösbar (da es NP-schwer ist). Wir untersuchen, von welchen Faktoren die Laufzeit der Algorithmen abhängt und versuchen die Algorithmen bezüglich dieser Faktoren so zu optimieren, dass sie auf praktischen Instanzen schnell laufen.

In unserem Projekt haben wir zunächst die wichtigsten Konzepte der parametrisierten Komplexität kennengelernt. Wir haben anschließend, mit den Programmiersprachen C++, Java, Python und Rust, Konzepte und Algorithmen für das Cluster-Editing Problem entwickelt, implementiert und evaluiert.

Zur Projekt Webseite