Questions tagged [automorphism]
The automorphism tag has no usage guidance.
12 questions
10
votes
2
answers
2k
views
Computing the edge orbits of a graph (and discussing definitions)
A (vertex) automorphism in a graph $G=(V,E)$ is a permutation $\sigma$ of the vertices that preserves adjacency, namely $\sigma(u) \sigma(v) \in E$ if and only if $uv \in E$. The automorphisms of a ...
- 388
4
votes
1
answer
167
views
What automorphisms on a Markov Chain imply a uniform limiting distribution?
Consider an irreducible aperiodic Markov chain $M$, modeled as a connected directed graph with weighted edges. The existence of certain (graph) automorphisms on this Markov chain imply various ...
- 439
10
votes
2
answers
329
views
When polynomial GI implies polynomial (edge) colored GI?
Crossposted from MO.
(edge) colored graph isomorphism is GI which
preserves the colors (of edges if it is edge colored).
There are several reductions using transformations/gadgets
of (edge) colored ...
- 1,955
7
votes
1
answer
414
views
Complexity of counting poset automorphisms
A (finite) poset $P = (X, <)$, or partially ordered set, is a (finite) set $X$ equipped with a transitive antisymmetric relation $<$; it can be equivalently seen as a DAG $G = (X, E)$ that is ...
- 9,838
16
votes
1
answer
521
views
Counterexample for Corneil's efficient algorithm for Graph Isomorphism
In the paper An Efficient Algorithm for Graph Isomorphism by Corneil and Gotlieb, 1970 a conjecture was stated upon which the stated algorithm relied for solving GI in polynomial time. Namely:
that ...
- 568
6
votes
1
answer
339
views
Best lower bound for proof complexity of graph non-automorphism problem
Graph automorphism problem ( GA) of determining whether a graph has a nontrivial automorphism is a good candidate for a problem in NP-intermediate. I'm looking for references that study the ...
- 21.1k
10
votes
2
answers
666
views
Approximating non-trivial graph automorphism?
Graph automorphism is a permutation of graph nodes that induces a bijection on the edge set $E$. Formally, It is a permutation $f$ of nodes such $(u,v)\in E$ iff $(f(u),f(v))\in E$
Define an ...
- 21.1k
13
votes
1
answer
533
views
Is "Is a permutation p an automorphism of a graph in my set?" NP-complete?
Suppose we have a set S of graphs (finite graphs, but an infinite number of them) and a group P of permutations that acts on S.
Instance: A permutation p in P.
Question: Does there exist a graph g in ...
14
votes
1
answer
357
views
Generating Graphs with Trivial Automorphisms
I'm revising some cryptographic model. To show its inadequacy, I've devised a contrived protocol based on graph isomorphism.
It is "commonplace" (yet controversial!) to assume the existence ...
- 16.6k
23
votes
2
answers
1k
views
Relationship between symmetry and computational intractability?
The $k$-fixed point free automorphism problem asks for a graph automorphism which moves at least $k(n)$ nodes. The problem is $NP$-complete if $k(n)=n^c$ for any $c$>0.
However, If $k(n)=O(\log n)$...
- 21.1k
2
votes
1
answer
361
views
What is the most efficient algorithm to sample graphs with trivial automorphism groups ?
Let us call a graph "asymmetric" if it has no nontrivial automorphism group. http://en.wikipedia.org/wiki/Asymmetric_graph
I'm looking for an efficient way to compute a random asymmetric graph on a ...
- 21.1k
12
votes
1
answer
592
views
what are known bounds on complexity of nontrivial graph automorphism
Given any simple undirected graph G, it is nontrivial to determine if G has nontrivial (non-identity) automorphisms. But what are results on upper/lower bounds of this decision problem?
- 141