资源描述：
《求最小顶点覆盖的详细介绍》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、Chapter10ExtendingtheLimitsofTractabilitySlidesbyKevinWayne.Copyright@2005Pearson-AddisonWesley.Allrightsreserved.1CopingWithNP-CompletenessQ.SupposeIneedtosolveanNP-completeproblem.WhatshouldIdo?A.Theorysaysyou'reunlikelytofindpoly-timealgorithm.Must
2、sacrificeoneofthreedesiredfeatures.¢Solveproblemtooptimality.¢Solveprobleminpolynomialtime.¢Solvearbitraryinstancesoftheproblem.ThisChapter.SolvesomespecialcasesofNP-completeproblemsthatariseinpractice.210.1FindingSmallVertexCovers1VertexCoverVERTEXCO
3、VER:GivenagraphG=(V,E)andanintegerk,isthereasubsetofverticesS⊆Vsuchthat
4、S
5、≤k,andforeachedge(u,v)eitheru∈S,orv∈S,orboth.1627k=4S={3,6,7,10}38495104FindingSmallVertexCoversQ.Whatifkissmall?Bruteforce.O(knk+1).k¢TryallC(n,k)=O(n)subsetsofsizek.¢TakesO(kn
6、)timetocheckwhetherasubsetisavertexcover.GoalGoal.LimitexponentialdependencyonkegtoO(2Limitexponentialdependencyonk,e.g.,toO(2kkn).Ex.n=1,000,k=10.Brute.knk+1=1034⇒infeasible.Better.2kkn=107⇒feasible.Remark.Ifkisaconstant,algorithmispoly-time;ifkisasm
7、allconstant,thenit'salsopractical.5FindingSmallVertexCoversClaim.IfGhasnnodes,themaximumdegreeofanynodeisd,andthereisavertexcoverofsize≤k,thenGhasatmostkdedges.Pf.¢SupposeGhasavertexcoverSofsize≤k.¢EachnodeofScancoveratmostdedges.¢Thetotalcoverededges
8、is≤kd.Claim.IfGhasavertexcoverofsizek,ithas≤k(n-1)edges.Pf.Eachvertexcoversatmostn-1edges.▪62FindingSmallVertexCoversClaim.Letu-vbeanedgeofG.Ghasavertexcoverofsize≤kiffatleastoneofG−{u}andG−{v}hasavertexcoverofsize≤k-1.deletevandallincidentedgesPf.⇒¢S
9、upposeGhasavertexcoverSofsize≤k.¢Scontainseitheruorv(orboth).Assumeitcontainsu.¢S−{u}isavertexcoverofG−{u}.Pf.⇐¢SupposeSisavertexcoverofG−{u}ofsize≤k-1.¢ThenS∪{u}isavertexcoverofG.▪7FindingSmallVertexCovers:AlgorithmClaim.Thefollowingalgorithmdetermin
10、esifGhasavertexcoverofsize≤kinO(2kn)time.booleanVertex-Cover(G,k){if(Gcontainsnoedges)returntrueif(k==0)returnfalselet(u,v)beanyedgeofGa=Vertex-Cover(G-{u},k-1)b=Vertex-Cover(G-{v},k-1)returnaorb}Pf.¢Correctnessfollowsfromthelastclaim.k+1¢Ther
