Weighted F-free Edge Editing

Ein F-freier Graph besitzt keinen induzierten Teilgraphen aus einer Menge von verbotenen Teilgraphen F. Man kann Kanten in einem Graphen editieren (einfugen oder entfernen) um einen Graphen zu erreichen, der F-frei ist. Das Ziel von F-free Edge Editing ist es, eine minimale Menge an Editierungsoperation zu finden, die zu einem F-freien Graphen fuhren. Wir betrachten eine Generalisierung, Weighted F-free Edge Editing, die beliebige Kosten fur die Editierungsoperationen erlaubt. In dieser Arbeit fokussieren wir uns auf einen parametrisierten Suchbaumalgorithmus (FPT) mit den Editierungskosten als Parameter. Wir adaptieren bereits existierende Beschleunigungstechniken fur das ungewichteten Editieren fur den gewichteten Fall. Unter anderem betrachten wir Algorithmen zum Berechnen von unteren Schranken und Strategien fur die Auswahl von Teilgraphen zum Verzweigen. Auserdem diskutieren wir das Problem, die optimalen Editierungskosten fur den Suchbaumalgorithmus zu finden und prasentieren dafur zwei neue Suchstrategien. Zusatzlich behandeln wir einen Algorithmus basierend auf ganzahliger linearer Optimierung (ILP) und Methoden, die die Anzahl der generierten Bedingungen beschranken. Des Weiteren evaluieren wir die FPT und ILP Algorithmen und ihre Beschleunigungstechniken auf Protein-Protein Interaktionsgraphen fur F = {C4, P4}. Wir stellen fest, dass der FPT Algorithmus am meisten von dem Greedy-Algorithmus fur untere Schranken und der Auswahlstrategie “most adjacent” profitiert. Letztere praferiert Teilgraphen, die zu vielen anderen verbotenen Teilgraphen adjazent sind. Auch fanden wir heraus, dass der Algorithmus fur die untere Schranken, der auf lokaler Suche basiert, im gewichteten Fall grosere Probleme mit lokalen Maxima hat. Weiterhin bemerken wir, dass das Beschranken der Anzahl der generierten Bedingungen den ILP Algorithmus signifikant schneller werden lasst. Schlussendlich haben wir beide Losungsalgorithmen verglichen und kamen zum Schluss, dass der ILP Algorithmus konsistent besser ist als der FPT Algorithmus.