Dynamic Weighted Matching
The matching problem is one of the most prominently studied combinatorial graph problems having a variety of practical applications. A matching M of a graph G=(V,E) is a subset of edges such that no two elements of M have a common end point. In practice, graphs often change over time, e.g., edges are inserted or deleted in the graph as the time progresses. For example, new relations between objects of a network may be created or removed over time (for example in the Facebook network). Even though the matching problem can be solved in polynomial time, computing a new matching from scratch every time the graph changes is an expensive task on huge networks, as this ignores the previously computed information on the given instance. Another nice thesis project is to look at hypergraph matching.
Here, we want to bridge the gap between theory and practice that is currently observed for the fully dynamic maximal matching problem. In the project, we want to engineer several dynamic weighted maximal matching algorithms as well as an algorithm that is able to maintain the maximum weighted matching. To this end, we will look at two novel dynamic algorithms: a random walk-based algorithm as well as a dynamic algorithm that searches for augmenting paths. Without depth bound, the latter algorithm will be able to maintain a maximum matching.
On the theory side, it may be interesting to have a better analysis for the length of augmenting paths in random graphs or in general graphs with random insertions, as the optimum machting algorithms for the static case perform much better than what theory currently predits. This analysis project will be done jointly with Jun.-Prof. Felix Joos.
Finding a large (weighted matching), as stated above, is an important problem in practice. A generalization of graphs are hypergraphs. In a hypergraph an edge can connect more than two nodes. In contrast to the matching problem in graphs, the maximum (weight) matching problem in hypergraphs is NP-complete. In this project, we want to develop heuristics, problem reductions as well as a branch-and-reduce algorithm for the problem. The project will be jointly done with Jun.-Prof. Felix Joos.
Dynamic Independent Sets of Rectangles
Map labeling is a classical problem in cartography and geographic information systems (GIS) that asks to place labels for area, line, and point features, with the goal to select and place the maximum number of independent, i.e., overlap-free, labels. A practically interesting case is point labeling with axis-parallel rectangular labels of common size. In a fully dynamic setting, at each time step, either a new label appears or an existing label disappears. Then, the challenge is to maintain a maximum cardinality subset of pairwise independent labels with sub-linear update time. The project plans to engineer a new algorithm for the problem based on recent theoretical discoveries.
Biclique Search at Scale
Maximum biclique search, which finds the biclique with the maximum number of edges in a bipartite graph, is a fun-damental problem with a wide spectrum of applications indifferent domains. Here, we want to apply reductions to compute a problem kernel. Given the problem kernel, we will still be able to compute the optimum solution. However, since we want a fast solution, we want to apply a heuristic algorithm on the problem kernel.
Scalable/Memetic Weighted Independent Sets
The maximum weight independent set problem is an NP-hard problem that has attracted much attention in the combinatorial optimization community, due to its difficulty and its importance in many fields. Given a graph G=(V,E,w) with weight function w:V -> R+, the goal of the maximum weight independent set problem is to compute a subset of vertices I of V with maximum total weight, such that no vertices in I are adjacent to one another. Such a set is called a maximum weight independent set (MWIS). The maximum weight independent set problem has applications spanning many disciplines, including signal transmission, information retrieval, and computer vision. The goal of this project is to develop a scalable shared-memory parallel algorithm for the weighted independent set problem. Another option is to develop a memetic algorithm for the problem. See here for a german topic description.
Partitioning with Motifs
The graph partitioning problem is to partition a graph into a given number of balanced blocks, such that the number of edges running between the blocks is minimized. A new version of the problem is called partitioning with Motifs. Here, given a Motif, for example a triangle, the objective is changed to minimize the number of Motifs cut. The goal of this project is to engineer new algorithms for problems, in particular by using a weighting scheme, reductions and our graph partitioning framework KaHIP.
Machine Learning in Combinatorial Optimization
Machine learning is a powerful framework to do all kinds of things. Recently, machine learning has also been applied in combinatorial optimization. In this project, we want to learn reductions to reduce problems to a problem kernel. For example, in a graph, we may be able to decide which parts of it belong to a solution or not and hence remove them or (in case of a branch-and-reduce algorithm) branch on solution vertices first. There are a variety of problem where this may apply.
Hierarchical Partitioning Connected Partioning in Distributed Memory
In computer science, engineering, and related fields, graph partitioning is a common technique. For example, in parallel computing good partitionings of unstructured graphs are very valuable. In this area, graph partitioning is mostly used to partition the underlying graph model of computation and communication. Roughly speaking, nodes in this graph denote computation units, and edges represent communication. This graph needs to be partitioned such that there are few edges between the blocks (pieces). In particular, if we want to use k processors we want to partition the graph into k blocks of about equal size.
In this topic, together with Prof. Dr. P. Bastian, we want to engineer an algorithm that computes a hierarchically nested partition of a graph in a top down fashion. An additional constraint is that, due to the application, the blocks of the partition have to be connected. Lastly, if a sequential prototype has been successfully implemented, we want to transfer this algorithm into distributed memory.
Large k Graph PartitioningHere, like in the previous topic, we are also looking at graph partitioning. The particular focus here will be to engineer algorithm that can partition graphs into a very large number of blocks. For example, the partitioning problem will be significantly different if the number of blocks is set to k=n/2. In this case, the problem is in P (not in NP anymore) and is very much like graph matching.
Engineering A State-of-The-Art Max Clique SolverA clique C in an undirected graph G = (V, E), where V is the set of vertices and E is the set of edges, is a subset of V such that all its vertices are connected. The size of C is its cardinality. The maximum clique problem is to find a clique of maximum size in G. An important generalization of the maximum clique problem is the maximum weight clique problem, in which the graph has a weight function w that assigns a positive integer called weight to each vertex, and the weight of a clique C is defined to be the total weight of the vertices in C. The project has the goal to transfer reduction rules that have recently been developed for the dual weighted independent set problem to the max clique problem and thus improving the state of the art for the maximum weight clique problem. On the reduced problem, one can then apply an exact algorithm or a heuristic algorithm to solve the problem.
Dynamic Orbit PartitionA graph isomorphism is a mapping between the nodes of two graphs that preserves the edges. An automorphism is an isomorphism of a graph to itself. The (non-trivial) automorphisms intuitively represent the symmetries of a graph. Two nodes are in the same orbit, if there is an automorphism that maps one vertex to the other. The orbit partition is of interest for symmetry breaking techniques for various search problems. The goal of this project is to develop dynamic algorithms for computing the orbit partition, i.e., updating the orbit partition when the input graph changes faster than recomputing it from scratch.