Pseudoforest Partitions and the Approximation of Connected Subgraphs of High Density

This thesis deals with the problem of finding a subgraph of maximum density d* in a simple graph and related problems. The integral variant of the dual problem is to find an orientation with the smallest possible maximum indegree. This indegree is equal to the smallest number p of pseudoforests into which the graph can be partitioned, and is therefore called pseudoarboricity. It is shown that Kowalik's approximation scheme can be employed to accelerate the balanced binary search of the Gabow-Westermann algorithm in order to obtain a runtime of O(m^{3/2}√log log p) for determining p, where m is the number of edges in the graph. A subgraph of density greater than ⌈d*⌉-1 can be determined within the same asymptotic runtime. In addition, the runtimes of several algorithms for determining p are compared experimentally. On current hardware, the computations can be carried out in minutes for social networks with hundreds of millions of edges. Building upon Kowalik's approximation scheme, an approximation scheme for the arboricity with the same asymptotic runtime is developed. In contrast to previous approaches, it does not only approximate the value of the arboricity, but also computes a corresponding forest partition. This is achieved using a fast conversion of k pseudoforests into k+1 forests. Based on the concept of maximum density, a mixed integer linear program (MILP) can be formulated for finding a connected subgraph that minimizes a linear function. This problem, which is closely related to the Steiner tree problem on graphs, is NP-complete in general. For the case where the number of vertices is required to be exactly k, the MILP is compared to an existing formulation, the generalized subtour elimination constraints (GSEC), both in theory and in practice. Another topic under scrutiny is the approximation of the Steiner tree problem on graphs with the bidirected cut relaxation (BCR), which is equivalent to GSEC. It is shown that the algorithm of Byrka et al. computes a 1.354-approximation if the instances do not contain Steiner claws. Furthermore, an idea for generating hard instances is presented, yet it does not result in improved lower bounds on the integrality gap of BCR.In dieser Arbeit werden das Problem, in einem einfachen Graphen einen Subgraphen mit maximaler Dichte d* zu finden, sowie verwandte Probleme diskutiert. Die ganzzahlige Variante des dazu dualen Problems ist, eine Orientierung mit kleinstmöglichem maximalen Eingangsgrad zu finden. Dieser Eingangsgrad ist gleich der kleinsten Anzahl an Pseudowäldern, in die der Graph zerlegt werden kann, und wird daher als Pseudoarborizität p bezeichnet. Es wird gezeigt, wie Kowaliks Approximationsschema dazu verwendet werden kann, die balancierte binäre Suche des Algorithmus von Gabow und Westermann zu beschleunigen und eine Laufzeit von O(m^{3/2}√log log p) für die Bestimmung von p zu erreichen, wobei m die Anzahl der Kanten des Graphen ist. Ein Subgraph mit Dichte größer ⌈d*⌉-1 kann mit derselben asymptotischen Laufzeit bestimmt werden. Es werden zudem Laufzeiten verschiedener Algorithmen zur Bestimmung von p experimentell verglichen. Mit aktueller Hardware können die Berechnungen für soziale Netzwerke mit hunderten Millionen Kanten in wenigen Minuten ausgeführt werden. Aufbauend auf Kowaliks Approximationsschema wird ein Approximationsschema für die Arborizität eines Graphen mit derselben Laufzeit entwickelt. Im Gegensatz zu früheren Ansätzen approximiert dieses nicht nur den Wert der Arborizität, sondern berechnet auch eine dazugehörige Zerlegung in Wälder. Dies wird durch eine schnelle Konvertierung von k Pseudowäldern in k+1 Wälder erreicht. Basierend auf dem Konzept der maximalen Dichte kann ein gemischt-ganzzahliges lineares Programm (MILP) aufgestellt werden, um zusammenhängende Subgraphen zu finden, die eine lineare Funktion minimieren. Dieses Problem, das eng mit dem Steinerbaumproblem auf Graphen verwandt ist, ist im Allgemeinen NP-schwer. Für den Fall, dass die Anzahl der Knoten des Subgraphen genau k betragen soll, wird das MILP mit einer anderen bestehenden Formulierung, den generalized subtour elimination constraints (GSEC), sowohl theoretisch als auch experimentell verglichen. Eine weiteres Thema, das beleuchtet wird, ist die Approximation des Steinerbaumproblems auf Graphen mithilfe der bidirected cut relaxation (BCR), welche äquivalent zu GSEC ist. Es wird gezeigt, dass der Algorithmus von Byrka et al. eine 1,354-Approximation berechnet, wenn die Instanzen keine Steinerklauen enthalten. Es wird zudem eine Idee zur Generierung schwieriger Instanzen vorgestellt, die jedoch nicht in verbesserten unteren Schranken an das integrality gap von BCR resultiert