Bi-set

Let V be a finite ground set. A pair $$X=(X_O,X_I)$$ of subsets of V is called a bi-set if $$X_I \subseteq X_O \subseteq V$$ . We call $$X_O$$ the outer member of X and $$X_I$$ 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 $$X \cap Y=(X_O \cap Y_O,X_I \cap Y_I)$$ .
• The union of X and Y is $$X \cup Y=(X_O \cup Y_O,X_I \cup Y_I)$$ .
• We say that $$X \subseteq Y$$ if $$X \cap Y=X$$ and $$X \cup Y=Y$$ .
• X and Y are independent if $$X_O \cup Y_O=V$$ or $$X_I \cap Y_I=\emptyset$$ .

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

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