I searched the exchange and couldn't seem to find an answer to this.
I am trying to find an algorithm that, given a directed acyclic graph (DAG) $G = (N,E)$ with a single root node $r\in N$, finds all connected subgraphs $G_i\subseteq G$ that contain r.
What I've attempted so far
Consider the following DAG,
To start, we have the graph:
From the root, we should do a one-step search, including $m$ nodes, where $m$ ranges from $1$ to the number of children (of the root), in each subgraph. That is, the next set of subgraphs are:
For each one of the above subgraphs, should we just do another one-step search?
Does anyone know of a better algorithm for recursively counting all of the subgraphs? I'm now aware that there is likely no polynomial-time algorithm (thanks to Raphael's comment) and such an algorithm may have exponential complexity in the worst-case.