1
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ The $s\in s$ quantify in the equivalent statement should be "for some $s\in S$ depending on $v$." $\endgroup$
    – Colin McQuillan
    Oct 23, 2012 at 14:10

2 Answers 2

Reset to default
2
$\begingroup$

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)).

Improve this answer
$\endgroup$
6
  • $\begingroup$ So when directly converted to SAT it is counting IS (via 2SAT) with additional clauses (maybe again 2SAT)? $\endgroup$
    – joro
    Oct 23, 2012 at 14:31
  • $\begingroup$ 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? $\endgroup$
    – Felix Goldberg
    Oct 23, 2012 at 17:45
  • $\begingroup$ @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. $\endgroup$
    – Colin McQuillan
    Oct 23, 2012 at 19:12
  • $\begingroup$ @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^{'}$. $\endgroup$
    – Felix Goldberg
    Oct 24, 2012 at 10:40
  • $\begingroup$ @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? $\endgroup$
    – Colin McQuillan
    Oct 24, 2012 at 13:23
0
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ But not every independent set gives a quasi-kernel! $\endgroup$
    – Colin McQuillan
    Oct 23, 2012 at 14:07
  • $\begingroup$ Hm, indeed, I missed the additional condition... Thanks. $\endgroup$
    – joro
    Oct 23, 2012 at 14:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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