A *quasi-kernel* in a directed graph D is an independent subset of vertices $S$ so that for every $v \in V(D)-S$ either $v->s$ for some $s \in S$ or $v->w->s$ for some $w \in V(D)-S, s \in S$.


**Equivalently**, a set $S$ is a quasi-kernel if $d(s,t) \geq 2$ for every $s,t \in S$ and $d(v,s) \leq 2$ for every $v \in V(D)-S,s \in s$.


Chvatal & Lovasz had proved that every digraph has a quasi-kernel (very easy proof by induction) and Jacob & Meyniel had proved that a graph without a kernel has at least three quasi-kernels.


My question is: 



> 
> Is counting the number of
>  quasi-kernels NP-hard?
> 
> 
> 



Is number of quasi-kernels NP-hard?
Here's a reduction that works even if the directed graphs are required to be simple. I'll argue that there is a polynomial time algorithm which, given a graph $G$, outputs a directed graph $G'$ such that the number of independent sets in $G$ is the number of quasi-kernels in $G'$. Hence the number of quasi-kernels is NP-hard to calculate.


Take $G$, direct each edge arbitrarily, and for each vertex $v$ in $G$ add a directed path $v\rightarrow v'\rightarrow v''$ of length 2, directed away from the vertex. Call the resulting graph $G'$. (So $|V(G'|=3|V(G)|$ and $|E(G')|=|E(G)|+2|V(G|$.) Vertices of the form $v''$ must be in any quasi-kernel, and so vertices of the form $v'$ are not in any quasi-kernel, and the only condition on the original vertices are that two adjacent vertices cannot both be in a quasi-kernel. So the number of quasi-kernels in $G'$ is the number of independent sets in $G$.


This gives #P-completeness and NP-hardness of approximation (see M. Dyer, L.A. Goldberg, C. Greenhill and M. Jerrum, [On the relative complexity of approximate counting problems](http://cgi.csc.liv.ac.uk/~leslie/publications.html#relative), Algorithmica 38(3) 471-500 (2003)).


