Fooling Sets and the Spanning Tree Polytope Kaveh Khoshkhah, Dirk Oliver Theis∗ InstituteofComputerScience UniversityofTartu ofthe U¨likooli17,51014Tartu,Estonia {kaveh.khoshkhah,dotheis}@ut.ee 7 Mon Jan 2 11:58:01 EET 2017 1 0 2 n a Abstract J Inthestudyofextensionsofpolytopesofcombinatorialoptimizationproblems,anotori- 2 ousopenquestionisthatforthesizeofthesmallestextendedformulationoftheMinimum SpanningTreeproblemonacompletegraphwithnnodes. Thebestknownlowerboundis ] M Ω(n2),thebestknownupperboundisO(n3). Inthisnoteweshowthatthevenerablefoolingsetmethod cannotbeusedtoimprove D thelowerbound:everyfoolingsetfortheSpanningTreepolytopehassizeO(n2). . s Keywords: Polyhedral Combinatorial Optimization, Extended Formulations, Lower c Bounds. [ 1 v 1 Introduction 0 5 ([n]) 3 The Spanning Tree polytope Pn has as its vertices the characteristic vectors R 2 of edge- setsoftreeswithnodeset[n]:={1,...,n}. Acompletesystemofinequalitiesandequations 0 0 isthefollowing: . 1 0 xe =n−1 7 e∈X([n]) 1 2 : x ≤|S|−1 ∀S ⊂[n], |S|>1 v e i eX∈(S) X 2 [n] r x ≥0 ∀e∈ . a e (cid:18) 2 (cid:19) Thissystemhasexponentiallymanyfacet-defininginequalities. Thereisaclassicalextended formulation by Wong/Martin [10, 13] with O(n3) inequalities (and variables). A notorious open problem in polyhedral combinatorial optimization, highlighted by M. Goemans at the 2010 Carge`se Workshop on Combinatorial Optimization, asks whether or not an extended formulationwith o(n3)inequalitiesexists. TheonlyknownlowerboundisΩ(n2)—this isa “trivial”lowerbound(itisthedimensionofthespanningtreepolytope). One method for proving lower bounds to sizes of extended formulations is the so-called fooling-set method (see, e.g., [9]). For that method, one looks at the function f which maps every pair of an inequality and a solution to 0, if the solution satisfies the inequality with equation,andotherwiseto1. A foolingsetofsize r isa list ofpairsF = (s1,t1),...,(sr,tr) (cid:0) (cid:1) ∗SupportedbytheEstonianResearchCouncil,ETAG(EestiTeadusagentuur),throughPUTExploratoryGrant #620,andbytheEuropeanRegionalDevelopmentFundthroughtheEstonianCenterofExcellenceinComputer Science,EXCS. 1 such that f(s ,t ) = 1 for j = 1,...,r, and f(s ,t )f(s ,t ) = 0 for i 6= j. If a fooling set of j j i j j i sizer exists,theneveryextendedformulationmustcontainatleastr inequalities. Itisaneasyfolklorefactthateverypolytopehasafoolingsetofwhosesizethedimension ofthepolytope. Butfoolingsetlowerboundshavetheirlimitations. Mostimportantly,there can never be a fooling set larger than the square of the dimension of the polytope ([5]; see also[2,11]). However,sincethatboundisknowntobetight[7,6],andthedimensionofthe spanningtreepolytopeisΩ(n2),afoolingsetboundofΩ(n3)fortheSpanningTreepolytope is possible. A small improvement was made in [12], where a O(n8/3logn) upper bound for thelargestpossiblefoolingsetfortheSpanningTreepolytopeisshown. Inthisnote,weprovethatthelargestsizeofafoolingsetintheSpanningTreepolytope isO(n2). Theorem1. FoolingsetsforthespanningtreepolytopehavesizeO(n2). Webelievethatourtoolsmaybe usefulforotherattemptstogiveupperboundson sizes offoolingsets. 2 Proof of Theorem 1 We start by making precise the function f. Since the number of nonnegativity inequalities “x ≥0”isO(n2),andweaimforanO(n2)upperbound,wecanomitthem. Wedefine e S := S ([n] |S|>1 n (cid:12) o [n(cid:12)] T := T ⊂ (cid:12) T tree . n (cid:18) 2 (cid:19)(cid:12) o (cid:12) (cid:12) Thefunctionf isnowthefollowing: 0, ifthesub-forestofT inducedbyS isatree, f: S ×T : (S,T)7→ i.e.,T ∩ S isconnected;  2 1, otherwis(cid:0)e.(cid:1)  Weusetheterminology“S isconnectedinT”forthecasef(S,T)=0. NowletF = (S1,T1)...,(Sr,Tr) beafoolingsetofsizerforf. Wedefinean(r×r)-matrix H byHi,j :=f(S(cid:0)i,Tj). Wewillprove(cid:1)thefollowing. Lemma2(MainLemma). EverycolumnofH hasatmostn(n−1)zeroentries. TheMainLemmaimmediatelyimpliesTheorem1. ProofofTheorem1fromLemma2. ThatF isafoolingsetmeansthatH (has1sonthediag- onal, and)in each pair ofdiagonallyoppositeoff-diagonalentries, atleast oneis zero. So H hasatleastΩ(r2)zeroentries. ButtheMainLemmaimpliesthatH hasatmostO(rn2)zero entries. Intheremainderofthesection,wewillprovetheMainLemma. Westartwiththefundamentaldefinitionoftheproof. Definition 3 (Witness). Let S ∈ S, T ∈ T. A witness for f(S,T) = 1 is a triple (a,x,b) of nodeswhichsatisfies (a) a,b∈S,x∈/ S;and (b) xliesonthe(unique)pathinT betweenaandb. 2 Let us justify the terminology. Clearly, if a witness exists, S cannot be connected in T, andhencef(S,T)=1. Ontheotherhand,iff(S,T)=1,i.e.,thesub-forestofT inducedbyS has multiple connected components, then there is a node x ∈/ S with the property that for everya ∈ S thereis ab ∈ S such thatx lieson thepath in T betweena andb. (To findsuch anxshrinktheconnectedcomponentsto“supernodes”,andletxbe any(non-shrunk)node on a path between two “super nodes”.) Hence, a witness for f(S,T) = 1 exists if and only if f(S,T)=1. Clearly,if(a,x,b)isanwitnessforf(S,T)=1,thensois(b,x,a). Lemma4. If(a,x,b)isawitnessforbothf(S ,T )=1andf(S ,T )=1theni=j. i i j j Proof. If(a,x,b)isawitnessforbothf(S ,T )=1andf(S ,T )=1,thenitisalsoawitness i i j j for both f(S ,T ) = 1 and f(S ,T ) = 1. But since F is a foolingset, this can only happen if i j j i i=j. Lemma 5. Let S ∈ S, T ∈ T, and a,b,c ∈ S. If at least one of (a,x,b), (b,x,c), (c,x,a) is a witnessforf(S,T)=1,thenatleasttwoofthemare. Proof. Condition (a) of Definition 3 is satisfied by either none or all of the triples. As for Condition (b), if say, x were on the path between a and b in T, but x was neither on the pathbetweenbandcnoronthepathbetweencanda,thenT wouldhavetwodistinctpaths betweenaandb,onethroughxandoneavoidingx—acontradiction. Lemma 6. LetS ∈ S, T,T′ ∈ T,andx ∈ [n] suchthatW 6= ∅andS is connectedinT′. x,S,T Thenthereisanedge{a,b}∈T′∩ S with(a,x,b)∈W . 2 x,S,T (cid:0) (cid:1) Proof. ConsiderthetreeQwithnodesetS andedgesetT′∩ S . Amongallpairs{a,b}with 2 (a,x,b) ∈ Wx,S,T take oneforwhichthedistance betweena a(cid:0)nd(cid:1)bin Qisminimal. Weclaim that{a,b}∈ Q. Indeed,byLemma5,iftherewasaconthepath inQbetweenaandbwith c∈/ {a,b},thenforatleastoneof{a,c}or{c,b}thecorrespondingtripletwithxinthemiddle isinW ,andthedistanceinQisshorter. x,S,T Foreveryx∈[n](anode)andk ∈[r](acolumnofH),denotebyZ thesetofi∈[r](rows x,k ofH)forwhich • S isconnectedinT ;and i k • thereexista,b∈S suchthat(a,x,b)isawitnessforf(S ,T )=1. i i i Lemma7. Foreveryx∈[n]andk ∈[r],wehave|Z |≤n−1. x,k Proof. For each i ∈ Z , by Lemma 6, there is an edge {a ,b } ∈ T such that (a,x,b) ∈ x,k i i k W . x,Si,Ti ByLemma4,theedges{a ,b },i∈Z ,aredistinct. Hence|Z |≤n−1. i i x,k x,k TheproofoftheMainLemmaisnowalmostcomplete. ProofofLemma2. Letk ∈[r]betheindexofacolumnofH. Foreveryi∈[r]withf(S ,T )= i k 0, there is an x such that i ∈ Z . Hence the number of zero-entriesin that column of H is x,k atmost n |Z |, x,k xX=1 which,byLemma7isatmostn(n−1). 3 3 Conclusion and Outlook We have settled the question whether the fooling set method can be used to prove a non- trivial lower bound for the extension complexity (i.e., smallest number of inequality in an extended formulation) of the Spanning Tree polytope. There are two more, stronger, com- binatorial lower bounds which are frequently used: the rectangle covering number and the fractionalrectanglecoveringnumber. Thenextstepwouldbetofindoutifanyofthesegrow more quickly than n2. In summary, though, despite the interest in the problem (e.g., [1, 8]) andpartialresultsandapproaches(e.g.,[3,4]),theproblemisnowmoreopenthanever. Acknowledgments This research was supported by the Estonian Research Council, ETAG (Eesti Teadusagen- tuur),throughPUTExploratoryGrant#620. Wealsogratefullyacknowledgefundingbythe European Regional DevelopmentFund through the Estonian Center of Excellence in Com- puterScience,EXCS. References [1] LeRoy B. Beasley, Hartmut Klauck, Troy Lee, and Dirk Oliver Theis. Communication complexity,linearoptimization,andlowerboundsforthenonnegativerankofmatrices (DagstuhlSeminar13082). DagstuhlReports,3(2):127–143,2013. [2] Martin Dietzfelbinger, Juraj Hromkovicˇ, and Georg Schnitger. A comparison of two lower-boundmethodsforcommunicationcomplexity. Theoret.Comput.Sci.,168(1):39– 51, 1996. 19th International Symposium on Mathematical Foundations of Computer Science(Kosˇice,1994). [3] Yuri Faenza, Samuel Fiorini, Roland Grappe, and Hans Raj Tiwary. Extended formu- lations,nonnegativefactorizations,andrandomizedcommunicationprotocols. InInter- nationalSymposiumonCombinatorialOptimization,pages129–140.Springer,2012. [4] Samuel Fiorini, Tony Huynh, Gwenae¨l Joret, and Kanstantsin Pashkovich. Smaller extended formulations for the spanning tree polytope of bounded-genusgraphs. arXiv preprintarXiv:1604.07976,2016. [5] Samuel Fiorini, Volker Kaibel, Kanstantin Pashkovich, and Dirk Oliver Theis. Com- binatorial bounds on nonnegative rank and extended formulations. DiscreteMath., 313(1):67–83,2013. [6] Mirjam Friesen, Aya Hamed, Troy Lee, and Dirk Oliver Theis. Fooling-sets and rank. EuropeanJournalofCombinatorics,48:143–153,2015. [7] MirjamFriesenandDirkOliverTheis. Fooling-setsandrankinnonzerocharacteristic. In Jaroslav Nesˇetrˇil and Marco Pellegrini, editors, TheSeventhEuropeanConference onCombinatorics,GraphTheoryandApplications, volume 16 of CRMseries, pages 383–390.CRM,2013. [8] Hartmut Klauck, Troy Lee, Dirk Oliver Theis, and Rekha R Thomas. Limitations of convex programming: lower bounds on extended formulations and factorization ranks (DagstuhlSeminar15082). DagstuhlReports,5(2):109–127,2015. [9] EyalKushilevitzandNoamNisan. Communicationcomplexity. CambridgeUniversity Press,Cambridge,1997. [10] R.KippMartin. Usingseparationalgorithmstogeneratemixedintegermodelreformu- lations. OperationsResearchLetters,10(3):119–128,1991. 4 [11] MozhganPourmoradnasserandDirkOliverTheis. The(minimum)rankoftypicalfool- ingsetmatrices(preprint). arXiv:1608.07038,2016. [12] Stefan Welte. SizesofDescriptionsinLinearOptimization. PhD thesis, University of Marburg,2016. [13] RichardTWong. Integerprogrammingformulationsofthetravelingsalesmanproblem. In ProceedingsoftheIEEEinternationalconferenceofcircuitsandcomputers, pages 149–152.IEEEPressPiscataway,NJ,1980. 5