Monday, January 20, 2014
Technische Universität Berlin
Institut für Mathematik
Straße des 17. Juni 136
10623 Berlin
room MA 041
Lecture - 14:15
Abstract:
Despite a lot of fruitful research over the last decades, Graph isomorphism (GI) remains one of the few candidates for being a natural NP problem that neither is NP-complete nor in P.
In many practical applications, the input graphs have some special property that can be exploited to design an efficient isomorphism test. In fact, for almost all graph classes for which GI is decidable in polynomial time it turned out that there are also polylog time parallel (i.e. NC) or even logspace algorithms. Prominent examples of such classes are planar graphs or the intersection graphs of geometric objects like intervals or arcs on a circle.
In this talk we survey some recent logspace algorithms for computing canonical representations for interval graphs and some special circular arc graphs. As a consequence, the recognition, isomorphism and automorphism problems for these graphs are solvable in logspace.
Colloquium - 16:00
Abstract:
In the early 1970s, by work of Klee and Minty (1972) and Zadeh (1973), the Simplex Method, the Network Simplex Method, and the Successive Shortest Path Algorithm have been proved guilty of exponential worst-case behavior (for certain pivot rules). Since then, the common perception is that these algorithms can be fooled into investing senseless effort by 'bad instances' such as, e. g., Klee-Minty cubes. This talk promotes a more favorable stance towards the algorithms' worst-case behavior. We argue that the exponential worst-case performance is not necessarily a senseless waste of time, but may rather be due to the algorithms performing meaningful operations and solving difficult problems on their way. Given one of the above algorithms as a black box, we show that using this black box, with polynomial overhead and a limited interface, we can solve any problem in NP. This also allows us to derive NP-hardness results for some related problems.