My problem is to find an efficient algorithm for finding the
graph condensation of the transitive closure of implication graphs (G (
Vd U Vp, Ed U Ep)). For definitions of these terms see below.

Implication Graphs: are directed graphs.  The vertices of G can be
partitioned to two disjoint sets - Vd (direct vertices) and Vp (partial
partial vertex has only 1 child which is a direct vertex.

Parent Set(v): Set of all parent vertex of v.

directed path(v, w): if there is a set of direct edges (v, v1), (v1, v2,
... (vn, w), then there is a directed path from v to w.

Common Ancestor(v): of a partial vertex v. A direct vertex w is a common
ancestor of v iff there exists a directed path from w to all of the
vertices in the parent set of (v).

Transitive Closure: means finding all possible directed paths frm every
directed vertex to every other directed vertex. One should "assume" that there
exists a directed edge connecting (Common Ancestor(v), CHild(v)) for all
v in Vp, if there is not already one, while looking for directed paths.

Condensed Graph: If a subgraph comprising only direct edges and direct
vertex, is such that there is a directed edge from every vertex to every
other vertex, then the sub-graph should be condensed to one vertex.

The graph has 100,000 directed vertex and 75,000 partial vertex and is
sparse.

This completes the problem description. Though there are a few
research papers that addresses one of these problems but none them
really works for large graphs.

---

Clarification of Question by thisisraja-ga on 18 Apr 2005 19:45 PDT

Edges are partitioned into two disjoint sets Ed and Ep. Ed are direct
edges connecting a direct vertex to another direct vertex. Ep are
partial edges (directed) connecting a direct vertex to a partial
vertex. There are no edges connecting two partial vertex.

Child(v) : w is a child of v if there is a direct/partial edge connectng v,w.

Parent(v): w is a parent of v if there is a direct/partial edge connecting w,v.

A partial vertex has 2-5 parents and exactly one child.