(This is related to one of my academic projects)
Given a directed graph $G=(V,E)$, and $s_1\in V$ the initial state, Let's call a primitive path a path starting from the initial state and does not contain any edge twice (hence no loops)
we call a maximal primitive path a primitive path which is not a sub-path of another primitive path.
Example:
(Here the initial state is $0$)
- A primitive path in the graph above should always start by $01$
- $012563$, $0123$ and $015$ are primitive paths
- $0125634$ and $01234$ are maximal primitive paths
My questions are :
Question1 How many maximal primitive paths are there approximately in a graph using big O notation with parameters $|V|$ and $|E|$. (we can assume that |V| and |E| are very large, and in case of difficulty we can also assume the density of the the graph to be very small or $|E|\sim Const |V|$ )
for the example above the answer is $3$ ($01234$,$0125634$,$015634$)
The number of primitive paths is larger than $|T|$ and we can find some graphs in which it's exactly $|T|$, and some graphs in which it's approximately $e(|V|)!$ where $e\sim 2.71828...$. Now if we add maximality there are some graphs in which the answer is $1$ and others for which it's $|V|!$.
Now if we assume the density to be small, I don't know how to handle the problem.
Question2 How can we generate all maximal primitive paths efficiently?
There might be exponentially many maximal primitive paths – just take $n$ copies of graph given by $$V = \{0,1,2,3\},\quad\quad E = \{(0,1),(0,2),(1,3),(2,3)\},$$ and connect each $3$ to the next $0$ like this: $$ \begin{array} {}& &1&&&&1\\ &\nearrow&&\searrow&&\nearrow&&\searrow\\ 0 & &&&3\to\cdots\to 0 &&&& 3\\ &\searrow&&\nearrow&&\searrow&&\nearrow\\ & &2&&&&2 \end{array} $$ Each such a feature generates two valid choices. Such a graph has $O(|V|)$ edges, so it is sparse. Hence, unless you assume some special representation, generating all the possibilities seems impossible to do efficiently.
I hope this helps $\ddot\smile$