ENUMERATING THE KERNELS OF A DIRECTED GRAPH WITH NO ODD CIRCUITS

The problems of generating and counting the number of kernels of a dir ected graph G with no odd circuits are considered. An algorithm is des cribed for generating all distinct kernels of G. Its complexity is O(n m(k + 1)), where n, m and k are the number of vertices, edges and kern els of G. In contrast, we show that the problem of determining the num ber of kernels of G is #P-complete, even if the longest circuit of G h as length 2. A special case in which the counting problem can be solve d in polynomial time is also presented.