Tag - Graph isomorphism problem

Harm Derksen: Orbit Problems

31st March, 2023

Given a group G and two vectors v and w in a representation V, one can ask: do v and w lie in the same orbit? This is what we call the orbit problem. For the action of GLn on m-tuples of n × n matrices, the orbit problem translates to the module isomorphism problem for which there is a known polynomial time algorithm. In joint work with Visu Makam, we also gave a polynomial time algorithm for deciding whether the orbit closures of v and w intersect. We also have similar results for the left-right action of SLn × SLn on the space of m-tuples of matrices. These results are related to interesting problems in algebraic complexity theory, such as non-commutative rational identity testing. The graph isomorphism problem can also formulated as an orbit problem. No polynomial time algorithm for the graph isomorphism problem is known. I will discuss an algorithm for the graph isomorphism problem that is more powerful than the higher-dimensional Weisfeiler-Leman algorithm when it comes to distinguishing pairs of non-isomorphic graphs in polynomial time. (This algorithm could potentially be polynomial time, but we will not make such a bold claim.)

Saket Saurabh: Graph Isomorphism (on structured inputs)

18th January, 2022

The Graph Isomorphism (GI) problem is arguably the most widely known problem whose membership in P is unknown, but which is not believed to be NP-hard. While the existence of a polynomial-time algorithm on general graphs is still elusive, the complexity of Graph Isomorphism has been well understood on several classes of graphs, where structural properties of graphs in question have been used to design polynomial-time procedures solving the problem. In this talk we will look at some of these algorithms for Graph Isomorphism through the perspective of contributions of the speaker.