Timeline for Is Hankelability NP-hard?
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 23, 2017 at 12:37 | history | edited | CommunityBot |
replaced http://stackoverflow.com/ with https://stackoverflow.com/
|
|
| Apr 13, 2017 at 12:32 | history | edited | CommunityBot |
replaced http://cstheory.stackexchange.com/ with https://cstheory.stackexchange.com/
|
|
| Apr 29, 2015 at 22:53 | comment | added | Yoav Kallus | I realize what I wrote above is slightly wrong, but I think it works if you replace "cyclic graph" (by which I actually meant circulant) with "bipartite graph on 2n vertices with automorphism of order n that preserves the parts" | |
| Apr 29, 2015 at 21:31 | comment | added | Yoav Kallus | If I had a polynomial algorithm to decide Hankelability, it seems like I could use it to decide if a graph was cyclic or not, which would amount to determining whether its automorphism group had an element of order n. Since determining whether a graph has any nontrivial automorphism is just as hard as deciding if two graphs are isomorphic, it seems that your problem should also be at least this hard. | |
| Apr 29, 2015 at 20:57 | comment | added | Simd | @YoavKallus Yes that is right. | |
| Apr 29, 2015 at 20:56 | comment | added | Yoav Kallus | If you allow both rows and columns to be permuted, then Hankelability would be the same as Toeplitzability, yes? (en.wikipedia.org/wiki/Toeplitz_matrix) | |
| Apr 29, 2015 at 17:34 | comment | added | Simd | @PerAlexandersson It's an excellent question but the answer is, I don't know. That is I don't know what family of graphs this would correspond to. | |
| Apr 29, 2015 at 17:07 | comment | added | Per Alexandersson | Does Hankem matrices correspond to distance matrices for some nice family of graphs? If so, you are looking at a graph isomorphism problem, that is, to detect if a weighted graph is isomorphic to some graph in the "Hankel family"... | |
| Apr 29, 2015 at 17:02 | history | asked | Simd | CC BY-SA 3.0 |