Independent Set Vertex Cover

IndependentSetandVertexCover

HananAyad

1IndependentSetProblem

ForagraphG=(V,E),asetofnodesS ViscalledindependentifnotwonodesinSareconnectedbyanedgee∈E.TheIndependentSetproblemisto ndthelargestindependentsetinagraph.Itisnothardto ndsmallindependentsets,e.g.atrivialindependentsetisanysinglenode,butitishardto ndlargeindependentsets.

AsimpleexampleofagraphisshowninFigure1,wherethefollowingaretwoindependentsets,{A,E,G}and{B,C,E,G}.Thesecondisthelargestpossibleset.

Thedecisionversionoftheindependentsetproblemisstatedasfollows:GivenagraphGandanumberk,doesGcontainanindependentsetofsizeatleastk(i.e.,|S|≥k)?ThelargestkforwhichtheanswerisYESisthesizeofthelargestindependentsetinG.FindingsuchkrepresentstheoptimizationversionofIndependentSet.ItisevidentthatthedecisionversionoftheIndependentSetproblemispolynomiallyreducibletoitsoptimizationversion.Infact,usingbinarysearch,itispossibletosolvethedecisionproblemforO(logn)valuesofk.

Figure1:Agraphwithlargestindependentsetofsize4andsmallestvertexcoverofsize3.2VertexCoverProblem

GivenagraphG=(V,E),asetofnodesS Viscalledavertexcoverifeveryedgee∈EhasatleastoneendinS.Itisnothardto ndlargevertexcovers,e.g.,atrivialvertexcoveristhesetS=V.However,itishardto ndsmallvertexcovers.Thedecisionversionisstatedasfollows.GivenagraphGandanumberk,doesGcontainavertexcoverofsizeatmostk(i.e.,|S|≤k)?ThesameobservationsmentionedaboveontheoptimizationversionofIndependentSetapplyonVertexCover.Thedi erentisthatVertexCoverisaminimizationproblemwhereasIndependentSetisamaximizationproblem.

ForthegraphshowninFigure1,thefollowingarevertexcoverswherethesecondisthesmallestpossibleset{B,C,D,F}and{A,D,F}.

3RelativeDi culty

IndependentsetandVertexCoverwereprovedtobeequallyhard,eachbeingpolynomiallyreducibletotheother.ThisisduetothefactthatforagivengraphG,SisanindependentsetifandonlyifthesetV S(calledthecomplementofS)isavertexcover.Inwhatfollowsisaproofofthisfact.

1

第1页下一页