Hasse subgraph of a directed graph

Description of the problem

Let \(G = (V,E)\) be a directed graph. For the purposes of this note, assume that \(G\) has no multiple edges. In other words, assume \(E\) is a subset of \(V\times V\). We would like to understand the connectivity of \(G\) in its minimal form.

A subgraph \(H\) of \(G\) is called a Hasse subgraph if

1. \(H\) contains all the vertices of \(G\).
2. For any pair of vertices \(a,b\in V\), there is a path connecting \(a\) to \(b\) in \(G\) if and only if there is a path in \(H\) connecting \(a\) to \(b\).
3. If \((a,b)\) is a directed edge in \(H\), then every path connecting \(a\) to \(b\) in \(H\) contains the edge \((a,b)\).

Today, I would like to develop an algorithm which constructs a Hasse subgraph of a given directed graph.

A solution

I am going to use igraph python library to perform basic operations on graphs. Here is an example of a directed graph defined using the igraph library.

 import igraph

 g = igraph.Graph(4)
 g.to_directed()
 g.add_edges([(0,1),(1,2),(0,2),(2,3)])

One must give the number of vertices at the time of definition. The vertices are labelled as \(0,\ldots,n\) for a graph of size \(n+1\). Also, for igraph the default is a undirected graph, and one must declare a graph as directed in our case

The algorithm will remove an existing edge \((a,b)\) first, and then will check if there is a path between \(a\) and \(b\). If there is a path then the edge \((a,b)\) is not needed, and we put \((a,b)\) back in otherwise.

 def Hasse(G):
     for edge in G.get_edgelist():
         G.delete_edges([edge])
         paths = G.get_shortest_paths(edge[0],edge[1])
         if len(paths[0]) == 0:
            G.add_edges(edge)
     return G

In the python code above, the igraph library function get.shortest_paths(a,b) will return the list of shortest paths from the first vertex a to the second vertex b. If such a path exists then the edge \((a,b)\) is not needed.

Let us see how this algorithm works in some examples. Consider the following graph

 g = igraph.Graph(6)
 g.to_directed()
 g.add_edges([(2,4),(0,1),(0,2),(0,3),(3,4),(1,3),(1,5),(0,5),(1,2),(0,4),(4,5)])

Now, let us see how this graph looks like after we apply our algorithm.