From Egres Open
Jump to: navigation, search

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 [1][2].


  1. K. Bérczi, A. Frank, Variations for Lovász' submodular ideas, in: M. Grötschel, G.O.H. Katona (eds.), Building Bridges Between Mathematics and Computer Science, Bolyai Society, Springer 2008, pp. 137-164. EGRES Technical Report link.
  2. K. Bérczi, A. Frank, Packing Arborescences, EGRES Technical Report no. 2009-04.