Degree-Constrained Editing of Small-Degree Graphs

This thesis deals with degree-constrained graph modification problems. In particular, we investigate the computational complexity of DAG Realization and Degree Anonymity. The DAG Realization problem is, given a multiset of positive integer pairs, to decide whether there is a realizing directed acyclic graph (DAG), that is, pairs are one-to-one assigned to vertices such that the indegree and the outdegree of every vertex coincides with the two integers of the assigned pair. The Degree Anonymity problem is, given an undirected graph G and two positive integers k and s, to decide whether at most s graph modification operations can be performed in G in order to obtain a k-anonymous graph, that is, a graph where for each vertex there are k - 1 other vertices with the same degree. We classify both problems as NP-complete, that is, there are presumably no polynomial-time algorithms that can solve every instance of these problems. Confronted with this worst-case intractability, we perform a parameterized complexity study in order to detect efficiently solvable special cases that are still practically relevant. The goal herein is to develop fixed-parameter algorithms where the seemingly unavoidable exponential dependency in the running time is confined to a parameter of the input. If the parameter is small, then the corresponding fixed-parameter algorithm is fast. The parameter thus measures some structure in the input whose exploitation makes the particular input tractable. Considering Degree Anonymity, two natural parameters provided with the input are anonymity level k and solution size s. However, we will show that Degree Anonymity is W[1]-hard with respect to the parameter s even if k = 2. This means that the existence of fixed-parameter algorithms for s and k is very unlikely. Thus, other parameters have to be considered. We will show that the parameter maximum vertex degree is very promising for both DAG Realization and Degree Anonymity. Herein, for Degree Anonymity, we consider the maximum degree of the input graph. Considering DAG Realization, we take the maximum degree in a realizing DAG. Due to the problem definition, we can easily determine the maximum degree by taking the maximum over all integers in the given multiset. We provide fixed-parameter algorithms with respect to the maximum degree for DAG Realization and for Anonym E-Ins. The later is the variant of Degree Anonymity when only edge insertions are allowed as modification operations. If we allow edge deletions or vertex deletions as graph modification operations, then we can show that the corresponding variants of Degree Anonymity-called Anonym V-Del and Anonym E-Del-are NP-complete even if the maximum vertex degree is seven. Moreover, we provide strong intractability results for Anonym E-Del and Anonym V-Del proving that they remain NP-complete in several restricted graph classes. Studying the approximability of natural optimization problems associated with Anonym E-Del or Anonym V-Del, we obtain negative results showing that none of the considered problems can be approximated in polynomial time better than within a factor of n^(1/2) where n denotes the number of vertices in the input. Furthermore, for the optimization variants where the solution size s is given and the task is to maximize the anonymity level k, this inapproximability even holds if we allow a running time that is exponential in s. Observe that DAG Realization also can be seen as degree-constrained graph modification problem where only arc insertions are allowed: Starting with an arcless graph, the task is to insert arcs to obtain a realizing DAG for the given multiset. The above classification with respect to the parameter maximum degree shows that in graphs with small maximum degree the modification operation edge respectively arc insertion is easier than vertex or edge deletion. There is a plausible explanation for this behavior: When the maximum degree is small, then there is a high freedom in inserting edges or arcs as for a given vertex almost all other vertices can be chosen as new neighbor. Observe that for DAG Realization the additional requirement that the directed graph shall be acyclic restricts this freedom. In Anonym E-Ins, we do not have restrictions on this freedom. In fact, exploiting this freedom in our implementation for Anonym E-Ins, we show that our theoretical ideas can be turned into successful heuristics and lower bounds. Experiments on several large-scale real-world datasets show that our implementation significantly improves on a recent heuristic and provides (provably) optimal solutions on about 21 % (56 of 260) of the real-world data.
 
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.