資源描述：
《求最小頂點覆蓋的詳細介紹》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在行業(yè)資料-天天文庫。
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
