<p>Graph isomorphism for bipartite graphs is as hard as graph isomorphism for general undirected graphs. Considering bipartite posets (i.e., seeing bipartite graphs as Hasse diagrams of posets), you may see that counting the automorphisms of bipartite posets is as hard as counting the automorphisms of general undirected graphs.</p>

CC BY-SA 3.0
2014-05-15T22:44:20.357Z
Thanks! I tried to source your claims and indeed it seems that connected directed bipartite graphs are GI-complete: "Graph isomorphism problem",  V. N. Zemlyachenko, N. M. Korneenko, R. I. Tyshkevich, p. 49, refers to F. Schweiggert, "Zur isomorphie endlicher Graphen und Strukturen," seemingly unavailable online :(. So indeed, if counting automorphisms (or deciding their existence) on GI-complete families is of known complexity, this answers the question. Do you know the exact status of this? I'm currently trying to understand it, but it may not be straightforward (see edit to my question).
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2014-05-15T23:09:20.303Z
@a3nm: I don't know the origin, but to me it is a folklore. To see the claim, for a given undirected graph G, we create a bipartite graph H as follows. One partite set of H corresponds to the vertex set of G, and the other partite set of H corresponds to the edge set of G. Two vertices of H are adjacent if and only if the corresponding vertex and edge in G are incident. If G is connected, then H is also connected, and in a connected bipartite graph, the bipartition is unique. Hence, if the size of partite sets differ, an automorphism on H naturally translates to G.
Yoshio Okamoto
CC BY-SA 3.0
2014-05-16T22:46:36.467Z
OK, I buy that. $H$ should be oriented to match the poset case, but that's not a problem, and it even deals with the problem of differing partite set sizes. So, to rephrase your argument, there is a bijection between the automorphisms of a connected undirected graph and that of its directed bipartite edge-vertex incidence graph, and it preserves the fact of being fixpoint-free. So, as directed bipartite graphs can be seen as posets, there is a PTIME reduction from the counting and decision problems for connected undirected graphs to the analogous problems for posets.
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2014-05-16T22:53:26.050Z
To complete the picture, the complexity of deciding the existence of a fixed-point-free automorphism is NP-complete, and counting them is #P-complete, by http://epubs.siam.org/doi/abs/10.1137/0210002. Deciding the existence of a non-trivial automorphism is in NP and of unknown complexity, it is PTIME many-one reducible to isomorphism but the converse reduction is unknown. As for counting graph automorphisms overall, I am not sure what the complexity is... In all of this, the fact that the graph is connected is not crucial as you can always take the complement graph otherwise.
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2014-05-16T23:07:48.773Z
And last (and somewhat surprisingly), counting graph automorphisms is PTIME equivalent to graph isomorphism, according to R. Mathon, "A note on the graph isomorphism counting problem". (Thanks @Mc... for pointing me to this)
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2014-05-15T17:08:39.170Z
2014-05-15T17:08:39.170Z
Yoshio Okamoto
<p>A (finite) <em>poset</em> $P = (X, &lt;)$, or partially ordered set, is a (finite) set $X$ equipped with a transitive antisymmetric relation $&lt;$; it can be equivalently seen as a DAG $G = (X, E)$ that is transitive (whenever $(x, y) \in E$ and $(y, z) \in E$ then $(x, z) \in E$).</p>

<p>An <em>automorphism</em> of $P$ is a bijection $f$ from $X$ to $X$ such that $x &lt; y$ iff $f(x) &lt; f(y)$, in other words, both $f$ and $f^{-1}$ are order-preserving. The automorphism is <em>fixed-point-free</em> if there is no $x$ such that $f(x) = x$. Of course, the identity is always an automorphism (which is not fixed-point-free); other automorphisms are said to be <em>non-trivial</em>. Both automorphisms and fixed-point-free automorphisms are well-studied natural notions for posets; intuitively, posets that have non-trivial (fixed-point-free) automorphisms have a certain symmetry.</p>

<p><strong>Is anything known about the complexity of determining if a poset has a non-trivial automorphism, or fixed-point-free automorphism? Or the complexity of <em>counting</em> the number of automorphisms, or fixed-point-free automorphisms?</strong></p>

<p>For DAGs that are not transitive, determining if a DAG has a non-trivial automorphism is in NP and its complexity is unknown, like that of graph isomorphism (<a href="https://en.wikipedia.org/wiki/Graph_automorphism#Computational_complexity" rel="nofollow">source</a>). So, while the problem for transitive DAGs is still in NP, it should not be realistic to prove hardness as that would imply hardness of that open problem; but maybe the graph being transitive makes the problem easier (solvable in polynomial time)?</p>

<p>For other natural counting problems about posets, the problems of antichain counting (antichains are subsets of elements that are all pairwise incomparable), or of linear extension counting (linear extensions are the way to extend the partial order to a total order by adding more comparability relations), are all #P-complete to compute. (<a href="http://www.math.dartmouth.edu/~pw/M100W11/seth.pdf" rel="nofollow">source</a> and <a href="https://wsn-attack-detection.googlecode.com/svn/trunk/writeup/capstone/other_resources/adams_pre_and_proposal/pdfs/complexity%20counting%20cuts.pdf" rel="nofollow">source</a>). Is it also hard to count automorphisms, then?</p>

<cc.complexity-theory><counting-complexity><directed-acyclic-graph><partial-order><automorphism>
Complexity of counting poset automorphisms
Antoine Amarilli 'a3nm'
# Complexity of counting poset automorphisms

(Asked by: username_0 on 2014-05-14)

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 transitive (whenever $(x, y) \in E$ and $(y, z) \in E$ then $(x, z) \in E$).

An *automorphism* of $P$ is a bijection $f$ from $X$ to $X$ such that $x < y$ iff $f(x) < f(y)$, in other words, both $f$ and $f^{-1}$ are order-preserving. The automorphism is *fixed-point-free* if there is no $x$ such that $f(x) = x$. Of course, the identity is always an automorphism (which is not fixed-point-free); other automorphisms are said to be *non-trivial*. Both automorphisms and fixed-point-free automorphisms are well-studied natural notions for posets; intuitively, posets that have non-trivial (fixed-point-free) automorphisms have a certain symmetry.

**Is anything known about the complexity of determining if a poset has a non-trivial automorphism, or fixed-point-free automorphism? Or the complexity of *counting* the number of automorphisms, or fixed-point-free automorphisms?**

For DAGs that are not transitive, determining if a DAG has a non-trivial automorphism is in NP and its complexity is unknown, like that of graph isomorphism ([source](https://en.wikipedia.org/wiki/Graph_automorphism#Computational_complexity)). So, while the problem for transitive DAGs is still in NP, it should not be realistic to prove hardness as that would imply hardness of that open problem; but maybe the graph being transitive makes the problem easier (solvable in polynomial time)?

For other natural counting problems about posets, the problems of antichain counting (antichains are subsets of elements that are all pairwise incomparable), or of linear extension counting (linear extensions are the way to extend the partial order to a total order by adding more comparability relations), are all #P-complete to compute. ([source](http://www.math.dartmouth.edu/~pw/M100W11/seth.pdf) and [source](https://wsn-attack-detection.googlecode.com/svn/trunk/writeup/capstone/other_resources/adams_pre_and_proposal/pdfs/complexity%20counting%20cuts.pdf)). Is it also hard to count automorphisms, then?

**Tags:** cc.complexity-theory, counting-complexity, directed-acyclic-graph, partial-order, automorphism


---

## 1 answers

### Answer by username_1 on 2014-05-15. Score: 4 | Accepted answer

Graph isomorphism for bipartite graphs is as hard as graph isomorphism for general undirected graphs. Considering bipartite posets (i.e., seeing bipartite graphs as Hasse diagrams of posets), you may see that counting the automorphisms of bipartite posets is as hard as counting the automorphisms of general undirected graphs.

> **Comments:**
> **username_0**: Thanks! I tried to source your claims and indeed it seems that connected directed bipartite graphs are GI-complete: "Graph isomorphism problem",  V. N. Zemlyachenko, N. M. Korneenko, R. I. Tyshkevich, p. 49, refers to F. Schweiggert, "Zur isomorphie endlicher Graphen und Strukturen," seemingly unavailable online :(. So indeed, if counting automorphisms (or deciding their existence) on GI-complete families is of known complexity, this answers the question. Do you know the exact status of this? I'm currently trying to understand it, but it may not be straightforward (see edit to my question).  
> **username_1**: @a3nm: I don't know the origin, but to me it is a folklore. To see the claim, for a given undirected graph G, we create a bipartite graph H as follows. One partite set of H corresponds to the vertex set of G, and the other partite set of H corresponds to the edge set of G. Two vertices of H are adjacent if and only if the corresponding vertex and edge in G are incident. If G is connected, then H is also connected, and in a connected bipartite graph, the bipartition is unique. Hence, if the size of partite sets differ, an automorphism on H naturally translates to G.  
> **username_0**: OK, I buy that. $H$ should be oriented to match the poset case, but that's not a problem, and it even deals with the problem of differing partite set sizes. So, to rephrase your argument, there is a bijection between the automorphisms of a connected undirected graph and that of its directed bipartite edge-vertex incidence graph, and it preserves the fact of being fixpoint-free. So, as directed bipartite graphs can be seen as posets, there is a PTIME reduction from the counting and decision problems for connected undirected graphs to the analogous problems for posets.  
> **username_0**: To complete the picture, the complexity of deciding the existence of a fixed-point-free automorphism is NP-complete, and counting them is #P-complete, by http://epubs.siam.org/doi/abs/10.1137/0210002. Deciding the existence of a non-trivial automorphism is in NP and of unknown complexity, it is PTIME many-one reducible to isomorphism but the converse reduction is unknown. As for counting graph automorphisms overall, I am not sure what the complexity is... In all of this, the fact that the graph is connected is not crucial as you can always take the complement graph otherwise.  
> **username_0**: And last (and somewhat surprisingly), counting graph automorphisms is PTIME equivalent to graph isomorphism, according to R. Mathon, "A note on the graph isomorphism counting problem". (Thanks @Mc... for pointing me to this)  

---

