Tuyển tập các báo cáo nghiên cứu khoa học hay nhất của tạp chí toán học quốc tế đề tài: Combinatorial Game Theory Foundations Applied to Digraph Kernels. | Combinatorial Game Theory Foundations Applied to Digraph Kernels Aviezri S. Fraenkel Department of Applied Mathematics and Computer Science Weizmann Institute of Science Rehovot 76100 Israel fraenkel@ http fraenkel Submitted August 29 1996 Accepted November 21 1996 To Herb Wilf at the end of the first 5 Bar Mitzvahs At least 5 more in ever increasing joy and creativity Abstract 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 S1 S2 S3 such that Si lies in all the kernels S2 lies in the complements of all the kernels and on S3 the kernels may be nonunique. Thus in particular digraphs with a large number of kernels are those in which S3 is large possibly Si S2 0. We also show that G can be decomposed in O E time into two induced subgraphs G1 with vertex-set Si u S2 which has a unique kernel and G2 with vertex-set S3 such that any kernel K of G is the union of the kernel of G1 and a kernel of G2. In particular G has no kernel if and only if G2 has none. Our results hold even for some classes of infinite digraphs. 1 THE ELECTRONIC JOURNAL OF COMBINATORICS 4 no. 2 1997 R10 2 1. Introduction Modern combinatorial game theory has largely been a parasite it drew tools and results from fields such as logic computational complexity graph and matroid theory combinatorics algebra and number theory to generate results for itself. More recently it has also begun to contribute back to some of its benefactors such as to surreal numbers a subject created by John Conway Con1976 and to linear error-correcting codes which
