Timeline for Does it help for graph isomorphism to know power of the permutation matrix?
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 19, 2023 at 14:48 | comment | added | David Roberson | Upon further reflection, my statement that the subgroup generated by $P$ has size at most $n$ was remarkably stupid. math.stackexchange.com/questions/221211/… So maybe it makes sense to give the subgroup generated by $P$, though I suppose just generators should be given. | |
| Mar 19, 2023 at 14:32 | comment | added | David Roberson | By "permutation group of $P$, do you mean the cyclic subgroup generated by $P$? You could give the whole subgroup but this has size at most $n$ and then the problem becomes easy (simply try everything in the subgroup). You could add the promise that $Q \ne I$. But I think something more clever is needed. Otherwise $Q$ could be the matrix of the transposition $(1,2)$, and your two graphs could be any two arbitrary graphs that both have vertices $1$ and $2$ isolated. Then $Q$ doesn't really give you any information. Or maybe it tells you that the part of $P$ not acting on $\{1,2\}$ has odd order | |
| Mar 19, 2023 at 14:26 | comment | added | David Roberson | Well if you know that $P=Q$, then obviously it is trivial, and otherwise I am not sure the question makes sense. I am not an expert on complexity theory but I think you need to define a specific class of problems to ask if it is GI-hard, and it is assumed that knowledge of the class can be used to construct algorithms. So I don't think it makes sense to ask how hard is your problem when $P = Q$ but you don't know that $P=Q$. Apologies if I am wrong here. | |
| Mar 19, 2023 at 14:17 | history | edited | joro | CC BY-SA 4.0 |
Tried to avoid David's attack from the first comment
|
| Mar 19, 2023 at 14:13 | comment | added | joro | @DavidRoberson Thanks, you are right. It is still GI hard if $P=Q$. Do you have an idea how to avoid these cases? I am trying to define the permutation group of $P$. | |
| Mar 19, 2023 at 13:56 | comment | added | David Roberson | Couldn't $Q$ be the identity matrix and then this is as hard as the usual graph isomorphism? | |
| Mar 19, 2023 at 12:02 | history | asked | joro | CC BY-SA 4.0 |