Properties of minimal primitive digraphs

It is proved that, for $n\ge4$, the complexity of the determination of all $n$-vertex minimal primitive digraphs, which are parts of a given $n$-vertex primitive digraph $\Gamma$, coincides with the complexity of the recognition of a monotone Boolean function in $s$ variables where $s$ is the number of arcs $(i,j)$ in $\Gamma$ such that the vertex $i$ out-degree and the vertex $j$ in-degree exceed 1. It is found that, for $n\ge4$, all the primitive $n$-vertex digraphs with $n+1$ arcs are minimal graphs and there are minimal primitive $n$-vertex digraphs with the number of arcs from $n+2$ to $2n-3$. Minimal primitive $n$-vertex digraphs with $n+1$ and $n+2$ arcs are described.