4
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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$? $\endgroup$ – Noam Zeilberger Apr 6 '16 at 8:52
  • 2
    $\begingroup$ 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. $\endgroup$ – Noam Zeilberger Apr 6 '16 at 9:54
  • 2
    $\begingroup$ 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. $\endgroup$ – Emil Jeřábek supports Monica Apr 6 '16 at 11:20
  • 1
    $\begingroup$ 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). $\endgroup$ – Saeed Apr 6 '16 at 11:31
  • 3
    $\begingroup$ @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? $\endgroup$ – Noam Zeilberger Apr 7 '16 at 11:13
1
$\begingroup$

For complete graphs:

Order the possible-directed-edges as [[1,0],[2,0],...,[|V|-1,0],[0,1],[2,1],...,[|V|-1,1],[0,2],[1,2],...,[|V|-1,2],...,[0,|V|-1],[1,|V|-1]],[2,|V|-1],...,[|V|-2,|V|-1]], and imagine the perfect binary rooted tree whose levels correspond to initial segments of the possible-edges under that ordering,
and whose nodes correspond to which of those possible edges are/aren't present.
Do roughly a depth-first search on that tree without actually constructing the tree,
where you do ignore tree-edges that would make neither [u,v] nor [v,u] be present
and you can ignore tree-edges that would necessarily make [number_of_superorientation_edges_to_(i+1),number_of_superorientation_edges_from_(i+1)] lexicographically less than [number_of_superorientation_edges_to_(i),number_of_superorientation_edges_from_(i)].
Output the leaves that search reaches. ​ In Python:

n  =  number of vertices
possibilities = tuple([(i,j) for j in range(n) for i in range(n) if j!=i])

def might_be_valid_and_canonical_(choices):
 for v in range(n):
  for u in range(v):
   i = possibilities.index((v,u))
   if (i < len(choices)) and not choices[i]:
    j = possibilities.index((u,v))
    if (j < len(choices)) and not choices[j]:
     return False
 max_out_of,max_into,min_out_of,min_into = [0]*n,[0]*n,[0]*n,[0]*n
 for i in range(len(choices)):
  if choices[i]:
   u,v = possibilites[i]
   max_out_of[u] += 1
   max_into[v] += 1
   min_out_of[u] += 1
   min_into[v] += 1
 for (u,v) in possibilities[len(choices):]
   max_out_of[u] += 1
   max_into[v] += 1
 for i in range(n-1):
  if (max_into[i+1],max_out_of[i+1]) < (min_into[i],min_out_of[i]):
   return False
 return True

numedges = n*(n-1)

def superorientations():
 if n<2:
  raise NotImplemented
 choices,try_child = tuple(),0
 while True:
  LofC = len(choices)
  if LofC == numedges:
   yield [possibilities[i] for i in range(numedges) if choices[i]]
   try_child = int(choices[LofC-1])+1
   choices = choices[:LofC-1]
   continue
  if try_child == 0:
   if might_be_valid_and_canonical_(choices+(False,)):
    choices += (False,)
    continue
   try_child = 1
  if try_child == 1:
   if might_be_valid_and_canonical_(choices+(True,)):
    choices += (True,)
    try_child = 0
    continue
   try_child = 2
  if try_child == 2:
   LofC = len(choices)
   if LofC == 0:
    return
   try_child = int(choices[LofC-1])+1
   choices = choices[:LofC-1]




For nearly-complete graphs, you can do that to the subgraph consisting of the
vertices with degree |V|-1, and output the extensions of those to the whole graph.

$\endgroup$
  • $\begingroup$ Sorry, but what does "initial segments of the possible-edges under that ordering" refer to? $\endgroup$ – Han Xiao Apr 8 '16 at 3:27
  • $\begingroup$ It means "[subsets of the set of possible-edges] which are closed downwards under that ordering". ​ ​ $\endgroup$ – user6973 Apr 8 '16 at 3:36
  • $\begingroup$ Excuse my ignorance, can you explain your idea with a concrete example? For example, complete graph $K_3$. The ordered arc set should be $\{(1,0),(2,0),(0,1),(2,1),(0,2),(1,2)\}$. But what does the perfect binary tree look like? $\endgroup$ – Han Xiao Apr 8 '16 at 5:25
  • $\begingroup$ It looks like this, although the round numbers are backwards from how it would be traversed. ​ The top tree-node is where no choices have been made, and going [down&right]/[down&left] corresponds to the cases in which the current possible-superorientation-edge will/won't be in the output. ​ ​ ​ ​ $\endgroup$ – user6973 Apr 8 '16 at 11:42
  • $\begingroup$ Yes. Now I'm aware how the binary tree looks like exactly. But I still didn't get how to perform DFS search by ignoring tree-edges. Now for me, the solution seems to make the result even larger (from $3^{|E|}$ to $2^{2|E|}$). $\endgroup$ – Han Xiao Apr 8 '16 at 13:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.