I was reading the paper The Matching Problem in General Graphs is in Quasi-NC - Ola Svensson, Jakub Tarnawski. There the word mentioned in many places for example Definition 4.1 `$S$ is tight set for the face $F$'.

The perfect matching polytope is defined by the convex hull of the incidence vectors of all perfect matching in a graph. Now for a face $F$ of the polytope $\mathcal{S}(F)=\{S\subseteq V\mid |S|\equiv 1\bmod 2\text{ and }\forall\ x\in F\ x(\delta(S))=1\}$ where $\delta(S)$ denotes the set of all edges incident on $S$ and $x(T)=\sum_{e\in T}x_e$ where $T\subseteq E$. Then what does it mean by $S\in \mathcal{S}(F)$ is tight for the face $F$



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.