Some algorithmic problems in polytope theory

SomeAlgorithmiProblemsinPolytopeTheoryVolkerKaibel?andMarE.PfetshTUBerlinMA6{2Straedes17.Juni13610623BerlinGermanyfkaibel,pfetshgmath.tu-berlin.de1IntrodutionConvexpolyhedra,i.e.,theintersetionsofnitelymanylosedaÆnehalf-spaesinRd,areimportantobjetsinvariousareasofmathematisandotherdisiplines.Inpartiular,theompatonesamongthem(polytopes),whihequivalentlyanbedenedastheonvexhullsofnitelymanypointsinRd,havebeenstudiedsineanienttimes(e.g.,theplatonisolids).Polytopesappearasbuildingbloksofmoreompliatedstrutures,e.g.,in(ombina-torial)topology,numerialmathematis,oromputeraideddesign.Eveninphysispolytopesarerelevant(e.g.,inrystallographyorstringtheory).Probablythemostimportantreasonforthetremendousgrowthofinterestinthetheoryofonvexpolyhedraintheseondhalfofthe20thenturywasthefatthatlinearprogramming(i.e.,optimizingalinearfuntionoverthesolutionsofasystemoflinearinequalities)beameawidespreadtooltosolvepratialproblemsinindustry(andmilitary).Dantzig’sSimplexAlgorithm,developedinthelate40’s,showedthatgeometriandombinatorialknow-ledgeofpolyhedra(asthedomainsoflinearprogrammingproblems)isquitehelpfulforndingandanalyzingsolutionproeduresforlinearprogrammingproblems.Sinetheinterestinthetheoryofonvexpolyhedratoalargeextentomesfromalgorithmiproblems,itisnotsurprisingthatmanyalgorithmiquestionsonpolyhedraaroseinthepast.Butalsoinherently,onvexpoly-hedra(inpartiular:polytopes)giverisetoalgorithmiquestions,beausetheyanbetreatedasniteobjetsbydenition.Thismakesitpossibletoinvestigate(thesmalleronesamong)thembyomputerprograms(likethepolymake-systemwrittenbyGawrilowandJoswig,see[26℄and[27,28℄).Onehosentoexploitthispossibility,oneimmediatelyndsoneselfon-frontedwithmanyalgorithmihallenges.Thispaperontainsdesriptionsof35algorithmiproblemsaboutpoly-hedra.Thegoalistoolletforeahproblemtheurrentknowledgeaboutits?SupportedbytheDeutsheForshungsgemeinshaft,FOR413/1{1(Zi475/3{1).2VolkerKaibelandMarE.Pfetshomputationalomplexity.Consequently,ourtreatmentisfousedontheo-retialratherthanonpratialsubjets.Wewould,however,liketomentionthatformanyoftheproblemsomputerodesareavailable.Ourhoieofproblemstobeinludedisdenitelyinuenedbypersonalinterest.Wehavenotspentpartiulareortstodemonstrateforeahproblemwhyweonsiderittoberelevant.Itmaywellbethatthereaderndsotherproblemsatleastasinterestingastheoneswedisuss.Wewouldbeveryin-terestedtolearnaboutsuhproblems.Theolletionofproblemdesriptionspresentedinthispaperisintendedtobemaintainedasa(hopefullygrowing)listat~pfetsh/polyomplex/.Almostalloftheproblemsarequestionsaboutpolytopes.Insomeasestheorrespondingquestionsongeneralpolyhedraareinterestingaswell.Itanbetestedinpolynomialtimewhetherapolyhedronspeiedbylinearinequalitiesisboundedornot.ThisanbedonebyapplyingGaussianelim-inationandsolvingonelinearprogram.Roughly,theproblemsanbedividedintotwotypes:problemsforwhihtheinputare\geometrialdataandproblemsforwhihtheinputis\om-binatorial(seebelow).Atually,itturnedoutthatitwasratheronvenienttogrouptheproblemswehaveseletedintotheveategories\CoordinateDesriptions(Set.2),\CombinatorialStruture(Set.3),\Isomorphism(Set.4),\Optimization(Set.5),and\Realizability(Set.6).Sinetheboundaryomplexofasimpliialpolytopeisasimpliialomplex,studyingpolytopesleadstoquestionsthatareonernedwithmoregeneral(polyhe-dral)strutures:simpliialomplexes.Therefore,wehaveaddedaategory\BeyondPolytopes(Set.7),whereafewproblemsonernedwithgeneral(abstrat)simpliialomplexesareolletedthatareloselyrelatedtosimilarproblemsonpolytopes.Wedonotonsiderotherrelatedareaslikeorientedmatroids.Theproblemdesriptionsproeedalongthefollowingsheme.Firstinputandoutputarespeied.Thenasummaryoftheknowledgeonthetheoretialomplexityisgiven,e.g.,itisstatedthattheomplexityisunknown(\Open)orthattheproblemisNP-hard.Thisisdonefortheasewherethedimension(usuallyoftheinputpolytope)ispartoftheinputaswellasfortheaseofxeddimension;oftenthe(knowledgeonthe)omplexitystatusdiersforthetwoversions.Afterthat,ommentsontheproblemsaregiventogetherwithreferenes.Foreahproblemwetriedtoreportontheurrentstateofknowledgeaordingtotheliterature.Unlessstatedotherwise,allresultsmentionedwithoutitationsareeitheronsideredtobe\folkloreor\easytoprove.Attheendrelatedproblemsinthispaperarelisted.ForallnotionsinthetheoryofpolytopesthatweusewithoutexplanationwerefertoZiegler’sbook[65℄.Similarly,fortheoneptsfromthetheoryofomputationalomplexitythatplayaroleherewerefertoGareyandJohnson’slassialtext[24℄.WheneverwetalkaboutpolynomialredutionsthisreferstopolynomialtimeTuring-redutions.ForsomeoftheproblemsSomeAlgorithmiProblemsinPolytopeTheory3theoutputanbeexponentiallylargeintheinput.Fortheseproblemstheinterestingquestioniswhetherthereisapolynomialtotaltimealgorithm,i.e.,analgorithmwhoserunningtimeanbeboundedbyapolynomialinthesizesoftheinputandtheoutput(inontrasttoapolynomialtimealgorithmwhoserunningtimewouldbeboundedbyapolynomialjustintheinputsize).Notethatthenotionof\polynomialtotaltimeonlymakessensewithrespettoproblemswhihexpliitlyrequiretheoutputtobenon-redundant.Averyfundamentalresulti