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 (einfügen 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 führen. Wir betrachten eine Generalisierung, Weighted F-free Edge Editing, die beliebige Kosten für die Editierungsoperationen erlaubt.
In dieser Arbeit fokussieren wir uns auf einen parametrisierten Suchbaumalgorithmus (FPT) mit den Editierungskosten als Parameter. ... mehrWir adaptieren bereits existierende Beschleunigungstechniken für das ungewichteten Editieren für den gewichteten Fall. Unter anderem betrachten wir Algorithmen zum Berechnen von unteren Schranken und Strategien für die Auswahl von Teilgraphen zum Verzweigen. Außerdem diskutieren wir das Problem, die optimalen Editierungskosten für den Suchbaumalgorithmus zu finden und präsentieren dafür zwei neue Suchstrategien. Zusätzlich behandeln wir einen Algorithmus basierend auf ganzahliger linearer Optimierung (ILP) und Methoden, die die Anzahl der generierten Bedingungen beschränken.
Des Weiteren evaluieren wir die FPT und ILP Algorithmen und ihre Beschleunigungstechniken auf Protein-Protein Interaktionsgraphen für F = {C4, P4}. Wir stellen fest, dass der FPT Algorithmus am meisten von dem Greedy-Algorithmus für untere Schranken und der Auswahlstrategie “most adjacent” profitiert. Letztere präferiert Teilgraphen, die zu vielen anderen verbotenen Teilgraphen adjazent sind. Auch fanden wir heraus, dass der Algorithmus für die untere Schranken, der auf lokaler Suche basiert, im gewichteten Fall größere Probleme mit lokalen Maxima hat. Weiterhin bemerken wir, dass das Beschränken der Anzahl der generierten Bedingungen den ILP Algorithmus signifikant schneller werden lässt. Schlussendlich haben wir beide Lösungsalgorithmen verglichen und kamen zum Schluss, dass der ILP Algorithmus konsistent besser ist als der FPT Algorithmus.

An F-free graph does not contain an induced subgraph from a set of forbidden subgraphs F. Edges in a graph can be edited, i.e. removed or inserted, to reach a graph which is F-free. Finding a minimal set of such edits is the goal of F-free Edge Editing. In this thesis, we cover a generalization, Weighted F-free Edge Editing, which allows non-unit costs for each editing operation.
We focus on a fixed-parameter tractable (FPT) search tree algorithm with the editing cost as the parameter and adapt existing speed-up techniques for unweighted editing to the weighted case. For instance, we investigate algorithms for calculating lower bounds and subgraph selection strategies for branching. ... mehrAlso, we discuss the problem of finding the optimal editing cost for the search tree algorithm and propose two novel search strategies. Additionally, we cover an integer linear program (ILP) algorithm and methods for restricting constraint generation.
Moreover, we evaluate the FPT and ILP algorithms and their speed-up techniques on protein-protein interaction networks for F = {C4, P4}. The FPT algorithm benefits the most from the greedy lower bound and the “most adjacent” subgraph selection rule for branching. Also, we notice that the local search algorithm suffers from local maxima in the weighted case. Furthermore, we find that the restrictions on the generation of constraints lead to significant running time improvements for the ILP algorithm. Finally, we compare both solving algorithms and find that the ILP algorithm consistently manages to outperform the FPT approach.