The Total Matching Polytope generalizes the Stable Set Polytope and the Matching Polytope. In this paper, we give the perfect formulation for Trees and we derive two new families of valid inequalities, the balanced biclique inequalities which are always facet-defining and the non-balanced lifted biclique inequalities obtained by a lifting procedure, which are facet-defining for bipartite graphs. Finally, we give a complete description for Complete Bipartite Graphs.
翻译:完全匹配的多元性将稳定集聚和匹配的多元性概括为一般。 在本文中,我们给出了树木的完美配方,并产生了两个有效的不平等的新家庭:平衡的两极不平等,这种不平等始终是面面定的;通过提振程序获得的不平衡的取消的两极不平等,它们是两极图的面定。最后,我们给出了完整的两极图的完整描述。