Welcome
Our group's interests in both research and teaching are in various areas within the theory of computation, among them logic, complexity theory, algorithms, and automata theory, and especially the numerous connections between these areas.
Computer Science 7 is part of the Computer Science Department within the Faculty of Mathematics, Computer Science and Natural Sciences. There is a close collaboration with the Mathematical Foundations of Computer Science group.
News
Friday, 27.10.2017
13:30

14:15
We develop a new approach to solve the Graph Isomorphism Problem (GI) for input graphs G and H over the same vertex set V
that are close with respect to permutation distance. We show that if the input pair of graphs have permutation distance at
most k, then it is possible to construct in quadratic time an equivalent instance of size at most f(k), for a computable function
f, and decide whether there exists an isomorphism from G to H. Our algorithm is thus a kernelization algorithm and can be
used as a preprocessing step for inputs with low permutation distance. The algorithm consists of four steps. In the first
step we find a relabeling on the vertices of the symmetric difference $G triangle H$ as to restrict the maximal degree within
$G triangle H$. Next, we construct from the previous result (G',H) a subset of vertices that contains the set of vertices
that have to be relabeled in order to identify G' with H. This result in turn is used to construct a smaller instance for
Colored Graph Isomorphism. In the final step this colored instance is again transformed into an uncolored graph, which constitutes
our kernel instance.