Questions tagged [automorphism]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
16
votes
1answer
471 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 ...
16
votes
2answers
863 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)$ ...
14
votes
1answer
316 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 of BPP ...
13
votes
1answer
503 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 ...
11
votes
1answer
566 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?
10
votes
2answers
637 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 ...
10
votes
2answers
303 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 ...
7
votes
2answers
226 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 ...
7
votes
1answer
280 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 ...
6
votes
1answer
319 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 ...
4
votes
1answer
139 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 ...
2
votes
1answer
340 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 ...