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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented Oct 23, 2012 at 14:07
  • $\begingroup$ Hm, indeed, I missed the additional condition... Thanks. $\endgroup$
    – joro
    Commented Oct 23, 2012 at 14:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .