Optimization problems expressibility, approximatio

OptimizationProblems:Expressibility,ApproximationPropertiesandExpectedAsymptoticGrowthofOptimalSolutionsThomasBehrendtKevinComptonyErichGradelTR-93-002January1993AbstractWeextendtherecentapproachofPapadimitrouandYannakakisthatrelatestheapproximationpropertiesofoptimizationproblemstotheirlogicalrepresentation.OurworkbuildsonresultsbyKolaitisandThakurwhosytematicallystudiedtheexpressibilityclassesMaxnandMaxnofmaximizationproblemsandshowedthattheyformashorthierarchyoffourlevels.Thetwolowestlevels,Max0andMax1coincidewiththeclassesMaxSnpandMaxNpofPapadimitriouandYannakakis;theycontainonlyproblemsthatareapproximableinpolynomialtimeuptoaconstantfactorandthusprovidealogicalcriterionforapproximability.How-ever,therearecomputationallyveryeasymaximizationproblems,suchasMaximumConnectedComponent(MCC)thatfailtosatisfythiscriterion.Wemodifytheseclassesbyallowingtheformulaetocontainpredicatesthataredenableinleastxpointlogic.Inaddition,wemaximizenotonlyoverrelationsbutalsooverconstants.WecalltheextendedclassesMaxFPiandMaxFPi.TheproofofPapadimitriouandYannakakiscanbeextendedtoMaxFP1toshowthatallproblemsinthisclassareapproximable.Someproblems,suchasMCC,descendfromthehighestlevelintheoriginalhierarchytothelowestlevelMaxFP0inthenewhierarchy.ThusourextendedclassMaxFP1providesamorepowerfulsucientcriterionforapproximabilitythantheoriginalclassMax1.MathematischesInstitut,UniversitatBasel,Rheinsprung21,CH-4051Basel,Switzerland,[e-mail],UniversityofMichigan,AnnArborMI48109-2122,U.S.A.,[e-mail]classesandprovethatanumberofimportantproblemsdonotbelongtoMaxFP1.TheseincludeMaxClique,MaxIndependentSet,V-CDimensionandMaxCommonInducedSubgraph.Todothisweintroduceanewmethodthatcharacterizesratesofgrowthofaverageoptimalsolutionsizes.Forinstance,itisknownthattheexpectedsizeofamaximalcliqueinarandomgraphgrowslogarithmicallywithrespecttothecardinalityofthegraph.WeshowthatnoprobleminMaxFP1canhavethisproperty,thusprovingthatMaxCliqueisnotinMaxFP1.Thistechniqueisrelatedtolimitlawsforvariouslogicsandtotheprobabilisticmethodfromcombinatorics.Webelievethatthismethodmaybeofindependentinterest.Incontrasttotherecentresultsonthenon-approximabilityofmanymaximizationproblems,amongthemMaxClique,ourresultsdonotdependonanyunprovedhypothesisfromcomplexitytheory,suchasP6=NP.ii1IntroductionAlthoughthenotionofNP-completenesswasdenedintermsofdecisionproblems,theprimemotivationforitsstudyanddevelopmentwastheapparentintractabilityofalargefamilyofcombinatorialoptimizationproblems.NP-completenessofadecisionproblemrulesoutthepossibilityndinganoptimalsolutionofthecorrespondingoptimizationprobleminpolynomialtimeunlessP=NP.Itdoesnotexclude,however,thepossibilitythatthereareecientalgorithmswhichproduceapproximatesolutions.Infact,formanyoptimizationproblemswithNP-completedecisionproblems,therearesimpleandecientalgorithmsthatproducesolutionsdieringfromoptimalsolutionsbyatmostaconstantfactor.Forsomeproblems,thereevenexistso-calledpolynomial-timeapproximationschemes(Ptas),whichproduceapproximatesolutionstoanydesireddegreeofaccuracy.Forotherproblems,notablytheTravelingSalespersonProblem,theredonotexistecientapproximationsunlessP=NP(see[10]).Untilnowthe\structuralreasonsforthedierentapproximationpropertiesofNPoptimizationproblemshavenotbeensucientlyunderstood.PapadimitriouandYannakakis[21]providedanewperspectivebyrelatingtheapprox-imationpropertiesofoptimizationproblemstotheirlogicalrepresentation.ExploitingFagin’scharacterizationofNPbyexistentialsecondorderlogic[9],theydenedtwoclassesofoptimizationproblems,MaxSnpandMaxNp,andshowedthatallproblemsintheseclassesareapproximableinpolynomialtimeuptoaconstantfactor.TheyalsoidentiedahostofproblemsthatarecompleteforMaxSnpwithrespecttoso-calledL-reductions,whichpreservepolynomial-timeapproximationschemes.Veryrecently,theclassesMaxSnpandMaxNphavereceivedalotofattentionduetoresultsbyAroraetal.[2]showingthatproblemswhicharehardforMaxSnpcannothaveaPtas,unlessP=NP.WepresentthesyntacticcriterionofPapadimitriouandYannakakisinthemoregeneralformandnotationprovidedbyKolaitisandThakur[15].Denition1.1Recallthatn(respectivelyn)areprexclassesinrstorderlogic,con-sistingofformulaeinprexnormalformwithnalternatingblocksofquantiersbeginningwith9(respectively8).TheclassesMaxn(respectivelyMaxn)consistofmaximiza-tionproblemsQwhoseinputinstancesarenitestructuresAofaxedsignature,suchthatthecostofanoptimalsolutionofQoninputAisdenablebyanexpressionoptQ(A)=maxSjfx:Aj=(x;S)gjwhere(x;S)isan-formula(respectivelyan-formula)andwhereSarepredicatevariablesnotcontainedin.Examples.1.MaxCut(MC)istheproblemofdecomposingthevertexsetofagivengraphGintotwosubsetssuchthatthenumberofedgesbetweenthemismaximal.ItisinMax0:optMC(G)=maxUjf(x;y):Gj=Exy^(Ux$:Uy)gj:2.MaxSatistheproblemofndinganassignmentthatsatisesthemaximalnumberofclausesinagivenpropositionalformulainCNF.Suchaformulacanberepresentedby1astructureF=(U;P;N)withuniverseUconsistingoftheclausesandthevariables,andwi