Degree-Constrained Editing of Small-Degree Graphs

Diese Dissertation beschäftigt sich mit Graphmodifikationsproblemen mit Knotengradbedingungen. Insbesondere wird die Berechnungskomplexität der Probleme DAG Realization und Degree Anonymity untersucht. Hierbei ist bei DAG Realization eine Multimenge an Paaren von natürlichen Zahlen gegeben und die Frage ist ob ein gerichteter kreisfreier Graph (DAG) existiert der die Multimenge realisiert. Das heißt, jedes Zahlenpaar ist genau einem Knoten des DAG zuzuordnen und dessen Knotengrad, bestehend aus Eingangs- und Ausgangsgrad, soll den Zahlen in dem zugeordneten Paar entsprechen. Die Zielstellung des Degree Anonymity-Problems ist, gegeben ein ungerichteter Graph G und zwei natürliche Zahlen k und s, in G höchstens s Modifikationsoperationen durchzuführen, sodass ein k-anonymer Graph entsteht. Ein Graph ist k-anonym, wenn für jeden Knoten k ? 1 andere Knoten mit dem gleichen Knotengrad enthalten sind.
Sowohl DAG Realization als auch Degree Anonymity werden in dieser Arbeit als NP-vollständig klassifiziert. Das heißt, es gibt vermutlich keine Polynomzeitalgorithmen die jede Eingabeinstanz der Probleme lösen können. Daher wird eine Studie der parametrisierten Berechnungskomplexität durchgeführt um effizient lösbare Spezialfälle zu identifizieren die noch praktisch relevant sind. Das Ziel hierbei ist die Entwicklung von Festparameteralgorithmen bei denen der vermutlich unvermeidliche exponentielle Anteil in der Laufzeit auf einen Parameter der Eingabe begrenzt wird. [–] Ist der Parameter klein, so ist der entsprechende Festparameteralgorithmus schnell. Bei Degree Anonymity werden zwei Parameter in der Eingabe direkt mitgeliefert: die Anonymitätsstufe k und die Lösungsgröße s. Allerdings wird in dieser Arbeit gezeigt, dass Degree Anonymity W[1]-schwer bezüglich des Parameters s ist, selbst bei k = 2. Dies bedeutet, dass es sehr unwahrscheinlich ist, dass Festparameteralgorithmen für s und k existieren. Deshalb müssen andere Parameter untersucht werden. Der Parameter maximaler Knotengrad stellt sich für beide Probleme, DAG Realization und Degree Anonymity, als vielversprechend heraus. Hierbei wird bei Degree Anonymity der Maximalgrad des Eingabegraphen benutzt. Bei DAG Realization wird der Maximalgrad in einem realisierendem DAG genommen. Die Definition des Problems DAG Realization ermöglicht eine einfache Bestimmung des Parameters durch das Maximum aller Zahlen in der gegebenen Multimenge. Vorgestellt werden Festparameteralgorithmen bezüglich des Parameters Maximalgrad für die Probleme DAG Realization und Anonym E-Ins. Letzteres ist die Variante von Degree Anonymity bei der nur Kanteneinfügungen erlaubt sind. Die beiden Problemvarianten von Degree Anonymity, die nur Knoten- bzw. Kantenlöschungen erlauben, heißen Anonym V-Del bzw. Anonym E-Del und sind beide NP-vollständig in Graphen mit Maximalgrad sieben. Weiterhin bleiben Anonym V-Del und Anonym E-Del NP-vollständig auf stark eingeschränkten Graphklassen wie zum Beispiel Bäumen. Die Untersuchung der Approximierbarkeit von natürlichen Optimierungsvarianten von Anonym E-Del und Anonym V-Del ergibt ein ähnlich düsteres Bild, da keine der untersuchten Varianten in Polynomzeit besser approximiert werden kann als mit einem Faktor n1 / 2 , wobei n die Knotenanzahl ist. Diese Nichtapproximierbarkeit gilt für die Optimierungsprobleme bei denen die Lösungsgröße s vorgegeben ist und die Anonymitätsstufe k maximiert werden soll, selbst wenn eine in s exponentielle Laufzeit erlaubt wird.
Zu beachten ist, dass DAG Realization auch als nur Kanteneinfügungen erlaubendes Graphmodifikationsproblem mit Knotengradbedingungen angesehen werden kann: Ausgehend von einem kantenfreien Graphen ist die Aufgabe gerichtete Kanten einzufügen sodass ein realisierender DAG entsteht. Obiges Klassifizierungsresultat bezüglich des Parameters Maximalgrad zeigt, dass in Graphen mit kleinem Maximalgrad die Modifikationsoperation Kanteneinfügung einfacher ist als Knoten- oder Kantenlöschung. Dafür gibt es eine plausible Erklärung: In Graphen mit kleinem Maximalgrad gibt es einen hohen Freiheitsgrad wie Kanten eingefügt werden können, da für einen gegebenen Knoten so gut wie alle anderen Knoten als neuer Nachbar gewählt werden können. Durch die zusätzliche Einschränkung bei DAG Realization, dass der gerichtete Graph kreisfrei sein muss, wird dieser Freiheitsgrad wieder eingeschränkt. Bei Anonym E-Ins existieren keine Einschränkungen für den Freiheitsgrad. Tatsächlich kann dieser Freiheitsgrad auch in einer in dieser Arbeit angegebenen Implementierung ausgenutzt werden, die die entwickelten theoretischen Ideen in erfolgreiche Heuristiken und einen Algorithmus zur Berechnung unterer Schranken umsetzt. Experimente auf mehreren großen Datensätzen belegen, dass die angegebene Implementierung eine aktuelle Heuristik verbessert und auf 21 % (56 von 260) der Datensätze (beweisbar) optimale Lösungen liefert.