On separation and adjacency problems for perfectly matchable subgraph polytopes of a graph (Q911485)

A subgraph F of a graph \(G=(V,E)\) is called a perfectly matchable subgraph (PMS) if F contains a set of independent edges covering all the vertices in F. For any \(S\subset V\) the independence vector is the vector \(x\in {\mathbb{R}}^{| V|}\) with coordinates \(x_ v=1\) if \(v\in S\) and \(x_ v=0\) if \(v\in V\setminus S\). The convex hull of the independence vectors of PMSs of G is called the PMS polytope of G. Theorem: Let x, y be vertices of the PMS polytope P, and let S and T be the corresponding PMSs. Then x and y are adjacent on P if and only if \(| S\cup T)\setminus (S\cap T)| =2.\) Another question discussed in the paper is the separation problem, which is to decide, for a vector \(x\in {\mathbb{R}}^{| V|}\), whether x is in the PMS polytope. It is shown that the separation problem for bipartite graphs can be solved by maximum flow algorithms.