What does the xor operator do in Stable matching

174 Views Asked by At

I was reading a paper and there was a $\oplus$ between two matching M and M’ in Stable matching problem , I know if it was a alternating path or cycle instead of M’ it means to switch C’s edges with M but cant figure it out about two matchings . Does that mean to exclude edges that happen in both ? Here’s the paper : Popular Matching in Stable Marriage Problem (ICALP 2009 I guess ) By Chien chung haung and Telikepalli Kavitha page 5 3rd paragraph

1

There are 1 best solutions below

2
On BEST ANSWER

In general, given two sets $S, T$, the likely meaning of $S \oplus T$ is $$ S \cup T \setminus (S \cap T) = \{x : x \in S \text{ xor } x \in T\}. $$ It's really just the xor operator, but on sets.

The effect on two matchings $M$ and $M'$ is that $M \oplus M'$ gives the set of edges that are in one matching, but not the other.

(Since every vertex has degree $0$ or $1$ in $M$, and also degree $0$ or $1$ in $M'$, the result is that it has degree $0$, $1$, or $2$ in $M \oplus M'$. This makes $M \oplus M'$ the union of paths and cycles, which is occasionally useful to know. For example, if $M'$ is a maximum matching, then the paths in $M \oplus M'$ give us a set of augmenting paths that can be used to turn $M$ into a maximum matching.)