Bi-set

Let V be a finite ground set. A pair [math]X=(X_O,X_I)[/math] of subsets of V is called a bi-set if [math]X_I \subseteq X_O \subseteq V[/math]. We call [math]X_O[/math] the outer member of X and [math]X_I[/math] the inner member of X. The following notions are used in relation to bi-sets:

• The intersection of two bi-sets X and Y is [math]X \cap Y=(X_O \cap Y_O,X_I \cap Y_I)[/math].
• The union of X and Y is [math]X \cup Y=(X_O \cup Y_O,X_I \cup Y_I)[/math].
• We say that [math]X \subseteq Y[/math] if [math]X \cap Y=X[/math] and [math]X \cup Y=Y[/math].
• X and Y are independent if [math]X_O \cup Y_O=V[/math] or [math]X_I \cap Y_I=\emptyset[/math].

If X is a bi-set, we say that an arc uv covers X if [math]u \in V \setminus X_O[/math] and [math]v \in X_I[/math]. An undirected edge uv covers X if one of its endnodes is in [math]V \setminus X_O[/math] and the other is in [math]X_I[/math].

For some examples of bi-sets in graph optimization, see Bérczi and Frank .