Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
The $s\in s$ quantify in the equivalent statement should be "for some $s\in S$ depending on $v$." –  Colin McQuillan Oct 23 '12 at 14:10

2 Answers 2

up vote 2 down vote accepted

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, Algorithmica 38(3) 471-500 (2003)).

share|improve this answer
    
So when directly converted to SAT it is counting IS (via 2SAT) with additional clauses (maybe again 2SAT)? –  joro Oct 23 '12 at 14:31
    
I am not sure I get it: not every independent set of $G$ will give you a quasi-kernel of $G^{'}$. It seems you have to start with a quasi-kernel of $G$ to get a quasi-kernel of $G^{'}$ - or am I missing some argument here? –  Felix Goldberg Oct 23 '12 at 17:45
    
@Felix: I am claiming that every independent set $I$ of $G$ gives a quasi-kernel $I\cup\{v''\mid v\in V(G)\}$ of $G'$, and that every quasi-kernel of $G'$ is of this form. –  Colin McQuillan Oct 23 '12 at 19:12
    
@Colin: Suppose that $G$ is an oriented $4$-cycle and let $I=\{v\}$ for any $v \in V(G)$. Then $I$ is not a quasi-kernel of $G$ and $I \cup \{v^{''}$ is not a quasi-kernel of $G^{'}$. –  Felix Goldberg Oct 24 '12 at 10:40
    
@FelixGoldberg: calling the vertices $\{v_1,v_2,v_3,v_4\}$, I am claiming that $\{v_1,v_1'',v_2'',v_3'',v_4''\}$ is a quasi-kernel of $G'$. Which condition fails? –  Colin McQuillan Oct 24 '12 at 13:23

If I understand correctly the condition $ d(s,t) \geq 2 $ means there is no outgoing edge from $s$ to $t$ which is very close to independent set in undirected graphs.

Here is an argument why your problem is #P complete via reduction from independent set.

Given undirected graph $G$ make it directed by adding both $(s,t)$ and $(t,s)$. The condition $ d(s,t) \geq 2 $ means $s$ and $t$ are not adjacent in $G$ and your set $S$ is an independent set for $G$.

Counting independent sets is #P complete.

share|improve this answer
1  
But not every independent set gives a quasi-kernel! –  Colin McQuillan Oct 23 '12 at 14:07
    
Hm, indeed, I missed the additional condition... Thanks. –  joro Oct 23 '12 at 14:20

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.