Grigni [15] Approximate TSP in Graphs with Forbidd

Grigni:[15]ApproximateTSPinGraphswithForbiddenMinorsMichelangeloGrigni?Dept.ofMathematicsandComputerScience,EmoryUniversity,AtlantaGeorgia30322,USA,[e-mail]:graphminor,genus,separator,spanner,TSP,approximationscheme.Abstract.Givenasinputanedge-weightedgraph,weanalyzetwoal-gorithmsforndingsubgraphswithlowtotaledgeweight.Therstal-gorithmndsaseparatorsubgraphwithasmallnumberofcomponents,andisanalyzedforgraphswithanarbitraryexcludedminor.Thesecondalgorithmndsaspannerwithsmallstretchfactor,andisanalyzedforgraphsinahereditaryfamilyG(k).Theseresultsimply(i)aQPTAS(quasi-polynomialtimeapproximationscheme)fortheTSP(travelingsalespersonproblem)inunweightedgraphswithanexcludedminor,and(ii)aQPTASfortheTSPinweightedgraphswithboundedgenus.1IntroductionInthetravelingsalespersonproblem(TSP)wearegivennsitesandtheirdistancematrix,andourgoalistondasimpleclosedtourofthesiteswithminimumtotaldistance.TheTSPhasdrivenbothpracticalandtheoreticalalgorithmre-searchforseveraldecades[9].MostvariantsareNP-hard,andthereforemuchattentionisgiventoapproximatesolutionsformetricTSP,wherethedistancematrixisametric(nonnegative,symmetric,andsatisfyingthetriangleinequal-ity).AnalgorithmofChristodes[6]ndsametricTSPsolutionwithcostatmost3=2timesoptimal.Wewouldpreferapolynomialtimeapproximationscheme(PTAS);thatis,foreach0,wewouldlikeapolynomialtimealgo-rithmwhichproducesasolutionwithcostatmost1+timesoptimal.However,metricTSPisMAXSNP-hardevenwhenalldistancesareoneortwo[12],andsothereissomepositive0suchthatndinga1+0approximationisNP-hard.Indeed,the3=2guaranteeofChristodeshasnotbeenimproved(althoughinpractice,otherheuristicsaremuchbetter).However,therehasbeenrecentprogressincertainrestrictedmetricspaces.In[8]wefoundaPTASfortheTSPonthenodesofanunweightedplanargraph,wherethemetricisgivenbyshortestpathlengthsinthegraph.Welatergeneralized[4]thistoallowdistancesdenedbynon-negativeedgecosts.Arora[3](alsoMitchell[11])gaveaPTASfortheTSPandrelatedproblems?SupportedbyNSFGrantnumberCCR-9820931.forpointsinaEuclideanspaceofxeddimension.Roughlyspeaking,alloftheseresultsdependontheabilitytondinexpensiveand\well-connectedseparators.Inthispaperweextendthemethodsof[4]fromplanargraphstolargergraphfamilies.Thisleadsustoageneralnotionofwell-connectedseparatorthatmayhaveotheralgorithmicapplications.Wepresenttwosubgraphndingalgorithms;inbothalgorithmsthegoalisalightsubgraph,meaningthatithaslowtotaledgeweight.InSection3wegiveanalgorithmndingalightseparatorsubgraphwithfewconnectedcomponents,ingraphsfromanyfamilywithanontrivialexcludedminor.InSection4wegiveanalgorithmndingalightspannerwithlowstretchfactor,ingraphsfromafamilyG(k),tobedened.Thisfamilyincludesgraphsofboundedgenus.Finally,inSection5wesketchaQPTAS(quasi-polynomialtimeapproxi-mationscheme)formetricTSPintwosituations.First,fortheshortestpathmetricinanunweightedgraphfromafamilywithanexcludedminor.Second,fortheshortestpathmetricinanedge-weightedgraphfromfamilyG(k),foranyxedk.BothschemesrunintimenO(loglogn).2PreliminariesAllgraphsinthispaperareundirectedandsimple.AgraphG=(V;E)isedge-weightedifithasanon-negativeweight(orlength)‘(e)oneachedgee2E;itisvertex-weightedifithasanon-negativeweightw(v)oneachvertexv2V.AsubgraphHofGinheritstheseweightsonitsedgesandvertices.ThetotaledgeweightandvertexweightinHaredenotedby‘(H)andw(H),respectively.ThenumberofconnectedcomponentsinHisdenoted#(H).WhenGisedge-weighted,dG(u;v)denotestheminimumlength‘(P)ofapathPconnectingendpointsuandv.Thisiszerowhenu=v,and+1whenuandvaredisconnected.G0=(V;E0)isaspanningsubgraphifitspanseachcomponentofG.ClearlydG(u;v)dG0(u;v);thestretchfactorsf(G0;G)istheminimumssuchthatdG0(u;v)sdG(u;v)forallu;v2V(itsucestoconsideronlyedgepairsfu;vg2E).Whensf(G0;G)s,wesaythatG0isans-spannerinG.GivenagraphG,aminorofGisagraphresultingfromsomesequenceofedgedeletion,vertexdeletion,oredgecontractionoperations(denotedGe,Gv,andG=erespectively).Sinceweonlyconsidersimplegraphs,wediscardself-loopsandparalleledges.WesayGhasanH-minor(denotedHG)ifGhasaminorisomorphictoH.AhereditarygraphpropertyisaclassPofgraphsclosedunderisomorphism,suchthatwheneverGisinP,soareitsminors.Inaseriesofpapers,RobertsonandSeymourshowthateveryhereditarygraphpropertyischaracterizedbyanitesetofforbiddenminors(see[7]foranoverview).TheprimeexampleisKuratowski’scharacterizationofplanargraphsbytheforbiddenminorsfK5;K3;3g.ForasubsetXofverticesinG,anX-apisthevertexsetofaconnectedcomponentofGX.Givenavertex-weightedgraphG,aseparatorisasubgraphSsuchthateveryV(S)-aphasweightatmostw(G)=2.Notethatseparatorsareusuallydenedasjustavertexset,butinthispaperweareinterestedinatradeobetween‘(S)and#(S).LetV(G)kdenotethecollectionofsetsofatmostkverticesinG.AhavenoforderkisafunctionassigninganX-aptoeachX2V(G)k,suchthat(Y)(X)wheneverXY2V(G)k.Givenavertex-weightedgraphGandanon-separatorvertexsubsetX,letw(X)denotetheuniqueX-apwithweightexceedingw(G)=2.IfXisaseparator,letw(X)=;.NotethatifGhasnoseparatorofsizek,thenw(restrictedtoV(G)k)isahavenoforderk.3AWell-ConnectedSeparatorA