Combinatorial game theory foundations applied to d

CombinatorialGameTheoryFoundationsAppliedtoDigraphKernelsAviezriS.FraenkelDepartmentofAppliedMathematicsandComputerScienceWeizmannInstituteofScienceRehovot76100,[e-mail]~fraenkel/fraenkel.htmlSubmitted:August29,1996;Accepted:November21,1996ToHerbWilfattheendofthe¯rst5BarMitzvahs:Atleast5moreineverincreasingjoyandcreativityAbstractKnowncomplexityfacts:thedecisionproblemoftheexistenceofakernelinadigraphG=(V;E)isNP-complete;ifallofthecyclesofGhaveevenlength,thenGhasakernel;andthequestionofthenumberofkernelsis#P-completeevenforthisrestrictedclassofdigraphs.Intheoppositedirection,weconstructgametheorytools,ofindependentinterest,concerningstrategiesinthepresenceofdrawpositions,toshowhowtopartitionV,inO(jEj)time,into3subsetsS1;S2;S3,suchthatS1liesinallthekernels;S2liesinthecomplementsofallthekernels;andonS3thekernelsmaybenonunique.Thus,inparticular,digraphswitha\largenumberofkernelsarethoseinwhichS3is\large;possiblyS1=S2=;.WealsoshowthatGcanbedecomposed,inO(jEj)time,intotwoinducedsubgraphsG1,withvertex-setS1[S2,whichhasauniquekernel;andG2,withvertex-setS3,suchthatanykernelKofGistheunionofthekernelofG1andakernelofG2.Inparticular,GhasnokernelifandonlyifG2hasnone.Ourresultsholdevenforsomeclassesofin¯nitedigraphs.1theelectronicjournalofcombinatorics4(no.2)(1997),#R1021.IntroductionModerncombinatorialgametheoryhaslargelybeenaparasite:itdrewtoolsandresultsfrom¯eldssuchaslogic,computationalcomplexity,graphandmatroidtheory,combinatorics,algebraandnumbertheorytogenerateresultsforitself.Morerecently,ithasalsobeguntocontributebacktosomeofitsbenefactors,suchastosurrealnumbers,asubjectcreatedbyJohnConway[Con1976],andtolinearerror-correctingcodes(whichislinearalgebra)[CoS1986],[Con1990],[BrP1993],[Fra1996].Inthispaperwedevelopsomebasicconceptsof2-playergametheory,andusethemtoshednewlightonthestructureofdigraphkernels.Connectionsbetweenkernelsandgame-theoryhavebeenexploredinthepast,seee.g.Berge[Ber1992];thenewelementhereseemstobetheuseofdrawpositionsforinvestigatingdigraphkernels.Infact,thesetofdrawpositionsappearstobethe\kernelofthekernels,i.e.,thepartwheremanyoftheinterestingpropertiesofthekernelsareconcentrated.Throughoutadigraphisa¯niteorin¯nitedirectedgraph,whichmaycontaincyclesorloops,unlessotherwisespeci¯ed.AkernelofadigraphG=(V;E)isasubsetKµVwhichisbothindependentanddominating.\IndependentmeansthatthesubgraphinducedbyKhasnoedges(soinparticular:noloops);and\dominating|thateveryvertexofV¡Khasafollower(successor)inK,i.e.,anedgeleadingintoK.IfGis¯nite,thedecisionproblemoftheexistenceofakernelisNP-complete,seeChv¶atal[Chv1973]andvanLeeuwen[VLe1976]forageneraldigraph,andFraenkel[Fra1981]foraplanardigraphwithindegrees·2,outdegrees·2anddegrees·3.Foranytighterconstraintstheproblemisclearlysolvableinlineartime.Itisfurtherknownthata¯nitedigraphallofwhosecycleshaveevenlengthhasakernel[Ric1953],andthatthequestionofthenumberofkernelsis#P-completeevenforthisrestrictedclassofdigraphs[SzC1994].Asanexample,consideradigraphwith2k+1verticesandk\blades,asdepictedinFig.1fork=4.Itclearlyhas2kkernels.Thecentervertexisinthekernelifandonlyifallitskfollowersarenot.Notethatthereisnovertexwhichisinallthekernelsorinthecomplementofallthekernelsforthisexample.Figure1.Thecasek=4ofadigraphwith2k+1verticesand2kkernels.theelectronicjournalofcombinatorics4(no.2)(1997),#R103Despitealltheine±ciencyandchaosexudedbytheseresults,weexhibitinthispaperanicestructureofdigraphkernels;andweshowthattheine±ciencypartcanbelocalizedandcontainedwithinawell-de¯nedinducedsubgraphofG.Moreover,ifGis¯nite,allofthiscanbedoneinO(jEj)steps.Speci¯cally,weshowthatforaclassofin¯nitedigraphsG=(V;E),thereexistsapartitionofVinto3subsetsS1;S2;S3,suchthatS1liesinallthekernels;S2liesinthecomplementsofallthekernels;andonS3thekernelsmaybenonunique.ForG¯nite,thepartitioncanbefoundinO(jEj)steps.IngeneralwecannotbemorepreciseaboutwhathappensinS3,aregionwheretheNP-completenessreigns,butinspecialcasesonemaybeabletosaysomething;seee.g.,theparagraphafterCorollary5.Notethatifadigraphhasa\largenumberofkernels,thenS3mustbe\large;possiblyS1=S2=;.ButS3maybelargewhenthereareonlyfewkernels:ifGisann-gon,thenS3=Vandthereare·2kernels.OfcourseS1=S2=;andS3=Visalwaysatrivialsolution,butformanydigraphs,especiallythosewithasmallnumberofedges,asfound,e.g.,inmanygame-graphs,S3issmall.Furthermore,weshowthatthereexistsadecompositionofGintotwoinducedsubgraphsG1,withvertex-setS1[S2,whichhasauniquekernel;andG2,withvertex-setS3,suchthatanykernelKofGistheunionofthekernelofG1andakernelofG2.Inparticular,Ghasnokernel(auniquekernel)ifandonlyifG2hasnokernel(auniquekernel).Itwillalsobecomeclearthattheseresultsareprovedmostnaturallyinagame-theoreticsetting;infact,theycanbeunderstoodbestintermsofthestrategyofthefollowingsimplecoin-pushinggameplayedonG.InitiallyacoinisplacedonsomevertexofG.Twoplayersalternatemoves.Amoveconsistsofslidingthecointoafollowervertexv,whichcouldbevitself,ifthemoveisalongaloop(\passing).Theplayer¯rstunabletomoveloses,andtheotherplayerwins.Inthec