Forming a canonicalization algorithm for representing graphs modulo isomorphism is clearly at least as hard as checking whether two graphs are, in fact, isomorphic (proof: just run the canonicalizer on both graphs and check if the results are equal).
And the graph isomorphism problem currently has no known polynomial-time solution.
As a theoretician it pains me to do this, but there are some decent algorithms out there for testing graph isomorphism and reducing to a canonical graph. In a previous life, when I was doing combinatorial design theory, I used Brendan McKay's nauty, which does exactly what you asked for -- given a graph, it returns a representation that is canonical up to isomorphism. I have no idea what algorithm it uses, but it was reasonably fast when I used it 7 or 8 years ago.
Because I just suggested that someone use an algorithm that is exponential time in the worst case, and moreover suggested that it was a pretty decent algorithm. Considering that I firmly believe in the fundamental importance of the worst case polytime vs. worst case exptime distinction, this was a painful suggestion to make.
I take it you don't like ML type inference? Worst case exptime, but in practice it is never anything other than linear-times-inverse-Ackermann unless you very, very carefully engineer your program to hit the bad case.
is (1) just an example or you actually have some problem which requires some sort of optimization over the space of "k-flats"? if you have such a problem, maybe you can exploit better the structure of it in order to simplify matters. for example, you can characterize the k-th largest eigenvalue of a hermitian matrix as the solution of a certain non-linear min-max problem in which the min is taken over the space of "k-flats" and the max is taken in that space (removing the origin, actually) that's the result of the Courant-Fischer Minimax Theorem, you can take a look at its statement here http://www.cs.tau.ac.il/~haima/gen_cf.pdf
my point is, exploiting the structure of your problem may lead to other more useful characterizations of the solution-set which wouldn't require you to actually try to find a representation for the set of k-flats... there are many different methods to compute eigenvalues...
Both of these are actual problems motivated by research ideas. #1 is like a regression problem: given points on a unit hypersphere centered at the origin, which k-dim "great circle" minimizes the residual sum of squares? The great circles correspond to the set of k-flats (aka "k-planes") through the origin (the circle is just the intersection of the flat and the sphere).
I don't see how eigenvalues might help here. Do you? I don't have a square matrix anywhere.
what do you mean by "residual sum of squares"? is it the sum of the squared distances to the k-flat? could it be the maximum of the squared distances? I will think about it...
Comments 34
Reply
Reply
Reply
See http://en.wikipedia.org/wiki/Smoothed_analysis
Reply
And the graph isomorphism problem currently has no known polynomial-time solution.
Reply
Reply
btw, who is this?
Reply
Reply
Reply
Reply
Reply
Reply
my point is, exploiting the structure of your problem may lead to other more useful characterizations of the solution-set which wouldn't require you to actually try to find a representation for the set of k-flats... there are many different methods to compute eigenvalues...
a propósito, sou eu, Ives...
Reply
Both of these are actual problems motivated by research ideas. #1 is like a regression problem: given points on a unit hypersphere centered at the origin, which k-dim "great circle" minimizes the residual sum of squares? The great circles correspond to the set of k-flats (aka "k-planes") through the origin (the circle is just the intersection of the flat and the sphere).
I don't see how eigenvalues might help here. Do you? I don't have a square matrix anywhere.
Reply
Ives
Reply
yup. You could use either geodesic distance (ideal) or orthogonal distance. It probably doesn't matter which.
Reply
Leave a comment