%Plain TeX -> Abstract for V4(2) R10
\magnification=1440\hsize=6true in \noindent{\bf 
 Aviezri S.\ Fraenkel}\bigskip\noindent
Combinatorial Game Theory Foundations Applied to 
Digraph Kernels \vskip.5cm\noindent
Known complexity facts: the decision problem of the 
existence of a kernel  in a digraph $G=(V,E)$ is
 NP-complete; if all of the cycles of $G$ have even 
length, then $G$ has a kernel; and the question of 
the number of kernels is $\#$P-complete even for this
 restricted class of digraphs. In the opposite direction, 
we construct game theory tools, of independent interest, 
concerning strategies in the presence of draw positions, 
to show how to partition $V$, in $O(|E|)$ time, into $3$ 
subsets $S_1,S_2,S_3$, such that $S_1$ lies in all the 
kernels; $S_2$ lies in the complements of all the kernels;
 and on $S_3$ the kernels may be nonunique. Thus, in
 particular, digraphs with a ``large'' number of kernels 
are those in which $S_3$ is ``large''; possibly
 $S_1=S_2=\emptyset$. We also show that $G$ can be decomposed,
 in  $O(|E|)$ time,  into two induced subgraphs $G_1$, 
with vertex-set $S_1\cup S_2$, which has a unique kernel;  
and $G_2$, with vertex-set $S_3$, such that any kernel
 $K$ of $G$ is the union of the kernel of $G_1$ and a
 kernel of $G_2$. In particular, $G$ has no kernel if
 and only if $G_2$ has none. Our results hold even for
 some classes of infinite digraphs.
\end