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 farConsider the following DAG,To start, we have the graph:$(\{1\},\varnothing)$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:$(\{1,2\},\{(1,2)\})$$(\{1,3\},\{(1,3)\})$$(\{1,4\},\{(1,4)\})$$(\{1,2,3\},\{(1,2),(1,3)\})$$(\{1,2,4\},\{(1,2),(1,4)\})$$(\{1,3,4\},\{(1,3),(1,4)\})$$(\{1,2,3,4\},\{(1,2),(1,3),(1,4)\})$For each one of the above subgraphs, should we just do another one-step search? QuestionsDoes 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.
Find all rooted subgraphs of a DAG
algorithms;graphs;enumeration;dag