<p>Given an undirected graph $G$, an <strong><em>orientation</em></strong> of $G$ is a directed graph obtained by assigning every edge a direction, a <strong><em>superorientation</em></strong> of $G$ is a directed graph obtained by orienting every edge in one direction or both ways.</p>

<p><strong>Aim</strong>: 
Enumerate all superorientations (isomorphic superorientations count as one) of an undirected graph.</p>

<p><strong>What for:</strong> 
Compute all <a href="http://users.encs.concordia.ca/~chvatal/kernel.html" rel="nofollow">kernels</a> (absorbing independent vertex sets) in as many digraphs as possible by using <a href="http://lemon.cs.elte.hu/egres/open/Polyhedral_description_of_kernels" rel="nofollow">polyhedral descriptions of kernels</a>, which are essentially linear programs (hence the problem can be solved efficiently).</p>

<p><strong>Current solution</strong> (for enumerating all superorientations)<strong>:</strong>
Given an undirected graph $G=(V,E)$,
for each edge $uv\in E$ generate 3 different arc sets $\{(u,v)\},\{(v,u)\} $ and $\{(u,v),(v,u)\}$ first.
Then enumerate all combinations of arc sets, which yields precisely $3^{|E|}$ digraphs in the result.</p>

<p><strong>Code in <em>Mathematica</em>:</strong></p>

<pre><code>SuperOrientation[g_Graph]:= Module[{el,tal,al},
  el=EdgeList[g];
  tal=DirectedEdge@@@el;
  al=Flatten/@Tuples[Subsets[#,{1,2}]&amp;/@Thread[List[tal,Reverse/@tal]]];
  Graph/@al];
</code></pre>

<p><strong>Problem:</strong>
Current solution gives too many isomorphic digraphs, especially for highly symmetric graphs.
I can delete isomorphic superorientations "efficiently" in <em>Mathematica</em> (the isomorphism test in <em>Mathematica</em> is implemented by <a href="http://www3.cs.stonybrook.edu/~algorith/implement/nauty/implement.shtml" rel="nofollow"><em>NAUTY</em></a>, which claims to be the fastest graph isomorphism test program in practice).
But testing graph isomorphism is still quite time consuming due to the fact that graph isomorphism problem is <em>NP</em>-intermediate.</p>

<p><strong>Question:</strong>
Is there a way to generate as less isomorphic graphs as possible in the enumeration before the isomorphism test?
It is unlikely to have a general solution.
But how about some special classes of graphs, say highly symmetric graphs.
Complete graphs, or subgraphs of complete graphs with only a few edges missing might be good starts, as my isomorphism test for superorientations of $K_7$ never ends. </p>

CC BY-SA 3.0
2016-04-06T06:53:10.980Z
Any asymmetric graph will admit $3^{|E|}$ non-isomorphic superorientations.  For the graphs that you are considering, do you expect there to be significantly fewer?
Noam Zeilberger
CC BY-SA 3.0
2016-04-06T07:13:37.253Z
@NoamZeilberger In fact I just want to reduce possible (super)orientations of symmetric graphs in my question. I have modified my question accordingly. Thank you for the comment.
hxiao
CC BY-SA 3.0
2016-04-06T08:52:58.553Z
I think it's going to depend a lot on how symmetric the graphs are.  Do you have any constraints on the underlying graph $G$?
Noam Zeilberger
CC BY-SA 3.0
2016-04-06T08:57:32.173Z
@NoamZeilberger Well, I'm afraid that underlying graphs don't have any extra constraints. But is there a way to orienting a graph by simply using its symmetry?
hxiao
CC BY-SA 3.0
2016-04-06T09:54:38.097Z
Do you mean if you already have the automorphism group of the graph?  That sounds reasonable, but computing the automorphism group is as hard as solving graph isomorphism.
Noam Zeilberger
CC BY-SA 3.0
2016-04-06T11:20:07.703Z
Any graph will have at least $3^{|E|}/|\mathrm{Aut}(G)|$ superorientations, which is still exponential unless the graph has only a few edges, and a huge automorphism group.
Emil Jeřábek
CC BY-SA 3.0
2016-04-06T11:31:44.773Z
With color refinement technique, quickly you can check whether two graphs are isomorphic, but it's false positive (maybe says two non-isomorphic graphs are isomorphic), btw it will restrict instances which are probably isomorphic. If your only concern is to keep the final list small, it may help (you can bruteforce over probably isomorphic graphs).
Saeed
CC BY-SA 3.0
2016-04-07T11:13:55.167Z
@HanXiao The question now feels very imprecise -- if you're still interested in feedback, then it might help to formulate a new question that describes more specifically what is the problem you are trying to solve.  What do you know about the underlying graph, and how is it represented?  Are you just interested in enumerating/counting superorientations, or are you using them to compute some other invariant of the graph?
Noam Zeilberger
CC BY-SA 3.0
2016-04-07T13:57:10.443Z
@NoamZeilberger Thank you very much for the suggestion. I edited my question again. If it is still confusing, please kindly let me know.
hxiao
<graph-theory><graph-algorithms>
Enumerating all (super)orientations of an undirected graph
hxiao
# Enumerating all (super)orientations of an undirected graph

(Asked by: username_0 on 2016-04-05)

Given an undirected graph $G$, an orientation of $G$ is a directed graph obtained by assigning every edge a direction, a superorientation of $G$ is a directed graph obtained by orienting every edge in one direction or both ways.
Aim: 
Enumerate all superorientations (isomorphic superorientations count as one) of an undirected graph.
What for: 
Compute all kernels (absorbing independent vertex sets) in as many digraphs as possible by using polyhedral descriptions of kernels, which are essentially linear programs (hence the problem can be solved efficiently).
Current solution (for enumerating all superorientations):
Given an undirected graph $G=(V,E)$,
for each edge $uv\in E$ generate 3 different arc sets $\{(u,v)\},\{(v,u)\} $ and $\{(u,v),(v,u)\}$ first.
Then enumerate all combinations of arc sets, which yields precisely $3^{|E|}$ digraphs in the result.
Code in Mathematica:
SuperOrientation[g_Graph]:= Module[{el,tal,al},
  el=EdgeList[g];
  tal=DirectedEdge@@@el;
  al=Flatten/@Tuples[Subsets[#,{1,2}]&/@Thread[List[tal,Reverse/@tal]]];
  Graph/@al];

Problem:
Current solution gives too many isomorphic digraphs, especially for highly symmetric graphs.
I can delete isomorphic superorientations "efficiently" in Mathematica (the isomorphism test in Mathematica is implemented by NAUTY, which claims to be the fastest graph isomorphism test program in practice).
But testing graph isomorphism is still quite time consuming due to the fact that graph isomorphism problem is NP-intermediate.
Question:
Is there a way to generate as less isomorphic graphs as possible in the enumeration before the isomorphism test?
It is unlikely to have a general solution.
But how about some special classes of graphs, say highly symmetric graphs.
Complete graphs, or subgraphs of complete graphs with only a few edges missing might be good starts, as my isomorphism test for superorientations of $K_7$ never ends.

**Tags:** graph-theory, graph-algorithms

> **Comments:**
> **username_1**: Any asymmetric graph will admit $3^{|E|}$ non-isomorphic superorientations.  For the graphs that you are considering, do you expect there to be significantly fewer?  
> **username_0**: @NoamZeilberger In fact I just want to reduce possible (super)orientations of symmetric graphs in my question. I have modified my question accordingly. Thank you for the comment.  
> **username_1**: I think it's going to depend a lot on how symmetric the graphs are.  Do you have any constraints on the underlying graph $G$?  
> **username_0**: @NoamZeilberger Well, I'm afraid that underlying graphs don't have any extra constraints. But is there a way to orienting a graph by simply using its symmetry?  
> **username_1**: Do you mean if you already have the automorphism group of the graph?  That sounds reasonable, but computing the automorphism group is as hard as solving graph isomorphism.  
> **username_2**: Any graph will have at least $3^{|E|}/|\mathrm{Aut}(G)|$ superorientations, which is still exponential unless the graph has only a few edges, and a huge automorphism group.  
> **username_3**: With color refinement technique, quickly you can check whether two graphs are isomorphic, but it's false positive (maybe says two non-isomorphic graphs are isomorphic), btw it will restrict instances which are probably isomorphic. If your only concern is to keep the final list small, it may help (you can bruteforce over probably isomorphic graphs).  
> **username_1**: @HanXiao The question now feels very imprecise -- if you're still interested in feedback, then it might help to formulate a new question that describes more specifically what is the problem you are trying to solve.  What do you know about the underlying graph, and how is it represented?  Are you just interested in enumerating/counting superorientations, or are you using them to compute some other invariant of the graph?  
> **username_0**: @NoamZeilberger Thank you very much for the suggestion. I edited my question again. If it is still confusing, please kindly let me know.  

---

## 0 answers

