Compact systems for T-join and perfect matching polyhedra of graphs with bounded genus (Q1180816)

The author is dealing with the question how to prove the existence of compact systems (constraint system `compressions') for special sets of polyhedra. A set \(\mathcal P\) of polyhedra \(P\in\mathbb{R}^{d(P)}\) has a compact system if there exists a polynomial \(f\) such that for each \(P\in{\mathcal P}\) there exists a matrix \((A,B,c)\) with integral coefficients, satisfying \(P=\{x\in\mathbb{R}^{d(P)}\mid\exists y[Ax+By\leq c]\}\) and size \((A,B,c)\leq f(d(P))\), where the size is given as usual by \(\sum_ i\sum_ j(1+\log_ 2(| m_{ij}|+1))\). He proves the following theorem which extends earlier results of \textit{F. Barahona} [``On cuts and matchings in planar graphs'', Rep. No. 88503-OR, Inst. Oper. Res., Univ. Bonn/Germany 1988]. Let \(S\) be a compact surface, then the set of perfect matching polyhedra of graphs embeddable on \(S\) has a compact system (the same holds for the set of \(T\)-join polyhedra of graphs embeddable on \(S\).