4
$\begingroup$

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

Example graph

$\endgroup$
  • 1
    $\begingroup$ It sounds like what you are looking for is a separator of size 2, is that correct? Two vertices $\{u, v\}$ such that if you remove them from the graph, the number of connected components goes up? $\endgroup$ – Pål GD Feb 25 '18 at 23:04
  • $\begingroup$ Related: cs.stackexchange.com/questions/88587/… . That problem (over a general DAG) works over a similar structure and the subgraphs it colors are almost the subgraphs you seek (one ancestor instead of two, can be solved by giving the two parents a single 'dummy' ancestor) $\endgroup$ – Discrete lizard Feb 26 '18 at 16:01
3
$\begingroup$

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.

$\endgroup$

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.