Regular Matroids Have Polynomial Extension Complexity
Manuel Aprile, Samuel Fiorini
Abstract
We prove that the extension complexity of the independence polytope of every regular matroid on n elements is O(n6). Past results of Wong and Martin on extended formulations of the spanning tree polytope of a graph imply a O(n2) bound for the special case of (co)graphic matroids. However, the case of a general regular matroid was open, despite recent attempts. We also consider the extension complexity of circuit dominants of regularmatroids, for which we give a O(n2) bound.
Topics & Concepts
MatroidMathematicsExtension (predicate logic)CombinatoricsPolytopeGraphic matroidMatroid partitioningDiscrete mathematicsSpanning treeUpper and lower boundsIndependence (probability theory)Time complexityComputer scienceMathematical analysisProgramming languageStatisticsAdvanced Graph Theory ResearchComplexity and Algorithms in Graphsgraph theory and CDMA systems