Pseudoforest Partitions and the Approximation of Connected Subgraphs of High Density
Date issued
Editors
Journal Title
Journal ISSN
Volume Title
Publisher
License
Abstract
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.