What graph theory algorithm(s) would help solve this problem?

Question

I have a directed graph with the following properties:

1. Except for a few special progenitor nodes, every node has two parent nodes
2. Any node can have any whole number of child nodes
3. The graph is generated such that no node is a descendant of itself in the following way: I starting with a few progenitor nodes (which have no parents) then randomly select two nodes and create a "child" node with directed edges going from each parent to the child. I repeat that step an arbitrary number of times.

I'd like to find an algorithm to efficiently identify subgraphs with the following properties:

1. The subgraph consists of two "parent" nodes and some or all of their descendants
2. Except for the two "parent" nodes in the subgraph, each node has both parents also contained in the subgraph (that is, if the subgraph were separated from the rest of the graph, no node would be separated from its parents, except for the two "parent" nodes).

It's easy to find a 3-node example of this type of subgraph - just take any two nodes and one of their mutual children. However, I'd like to be able to efficiently identify larger examples of these subgraphs.

I'd really appreciate some help pointing me in the right direction. I thought that what I need might be related to finding "weakly connected components", but I haven't made much progress, and my inexperience with graph theory makes it hard to figure out what to search for. Thanks!

PS: I've provided an example depiction of one of these graphs

Answer 1

Given two progenitor vertices $u$ and $v$, the following "modified flood fill" builds a set $P$ of additional vertices to include:

• While a vertex $x$ exists whose parents are both in the set $\{u, v\} \cup P$:
  • Add $x$ to $P$.

This will halt with $\{u, v\} \cup P$ being the largest possible set of vertices for the given pair of starting vertices. You want the subgraph this vertex set induces: To get that, just include every original edge that links two vertices in the set.

To do this reasonably efficiently, you could maintain 3 vertex sets $V_0, V_1, V_2$, where $V_i$ contains every vertex with exactly $i$ parents in $\{u, v\} \cup P$. Whenever some vertex $x$ is added to $P$, all of its neighbours in $V_0$ or $V_1$ are promoted to the next higher set (e.g., if some neighbour $y$ was in $V_1$, it is moved to $V_2$). These updates can be done in constant time per neighbour by using three doubly linked lists for $V_0, V_1, V_2$, as well as a length-$|V|$ array $A$ of pairs $(i, p)$: $A[u].i$ is the current set number (0, 1 or 2) for vertex $u$, and $A[u].p$ is a pointer to its linked list node. The main loop just reads from $V_2$ until no unread vertices remain. Each vertex and edge in the graph is processed only once, so the overall time for a single starting vertex pair is $O(|V|+|E|)$.

Thanks to D.W. for catching a problem in my first algorithm.