Research ArticleOpen AccessGoogle Scholar indexed
The Facets of the Bases Polytope of a Matroid and Two Consequences
Department of Mathematics and Statistics, Al Imam Mohamed Ibn Saud University (IMSIU), Riyadh, Saudi Arabia
- 1 Department of Mathematics and Statistics, Al Imam Mohamed Ibn Saud University (IMSIU), Riyadh, Saudi Arabia
Open Journal of Discrete Mathematics·Volume 08 (2017)·Pages 14–20·Published 24 November 2017·DOI10.4236/ojdm.2018.81002
Copy link · social · email
Abstract
Let M be a matroid defined on a finite set E and L ⊂ E . L is locked in M if and are 2-connected, and . In this paper, we prove that the nontrivial facets of the bases polytope of M are described by the locked subsets. We deduce that finding the maximum-weight basis of M is a polynomial time problem for matroids with a polynomial number of locked subsets. This class of matroids is closed under 2-sums and contains the class of uniform matroids, the Vámos matroid and all the excluded minors of 2-sums of uniform matroids. We deduce also a matroid oracle for testing uniformity of matroids after one call of this oracle.
KeywordsBases PolytopeFacetsLocked SubsetsMaximum-Weight Basis ProblemPolynomially Locked MatroidsMatroid OracleTesting Unformity of a Matroid
- Oxley, J.G. (1992) Matroid Theory. Oxford University Press, Oxford.
- Schrijver, A. (1986) Theory of Linear and Integer Programming. John Wiley and Sons, Chichester.
- Edmonds, J. (1971) Matroids and the Greedy Algorithm. Mathematical Programming, 1, 127-136. https://doi.org/10.1007/BF01584082
- Mayhew, D. (2008) Matroid Complexity and Nonsuccinct Descriptions. SIAM Journal on Discrete Mathematics, 22, 455466. https://doi.org/10.1137/050640576
- Robinson, G.C. and Welsh, D.J.A. (1980) The Computational Complexity of Matroid Properties. Mathematical Proceedings of the Cambridge Philosophical Society, 87, 29-45. https://doi.org/10.1017/S0305004100056498
- Chaourar, B. (2011) A Characterization of Uniform Matroids. ISRN Algebra, 2011, Article ID: 208478. https://doi.org/10.5402/2011/208478
- Jensen, P.M. and Korte, B. (1982) Complexity of Matroid Property Algorithms. SIAM Journal on Computing, 11, 184-190. https://doi.org/10.1137/0211014
- Giles, R. (1975) Submodular Functions, Graphs and Integer Polyhedra. PhD Thesis, University of Waterloo, Waterloo.
- Pulleyblank, W.R. (1989) Polyhedral Combinatorics. In: Nemhauser, G.L., et al., Eds., Handbooks in Operations Research and Management Science, Elsevier, Amsterdam, 371-446.
- Fujishige, S. (1984) A Characterization of Faces of the Base Polyhedron Associated with a Sub Modular System. Journal of the Operations Research Society of Japan, 27, 112-128. https://doi.org/10.15807/jorsj.27.112
- Feichtner, E.M. and Sturmfels, B. (2005) Matroid Polytopes, Nested Sets and Bergman Fans. Portugaliae Mathematica, 62, 437-468.
- Chaourar, B. (2008) On the Kth Best Basis of a Matroid. Operations Research Letters, 36, 239-242. https://doi.org/10.1016/j.orl.2007.05.007