Let $n \geq 2$ be an integer. Let \begin{align*} V &= \{(i, j); 1 \leq i, j \leq n \text{ and } i \neq j \} \\ E &= \{ \{v_1, v_2\}; v_1, v_2 \in V \text{ and } v_1 \neq v_2 \}. \end{align*} The graph $G = (V, E)$ is thus the complete graph on $|V| = n(n - 1)$ elements. Let $T$ denote the operation of interchanging $i$ and $j$. In other words, $T: V \to V$ maps $(i, j)$ to $(j, i)$. Define $\overline{V}$ to be the set of equivalence classes of $V$ under the group $\{ \operatorname{Id}, T \}$ and let $$ \overline{E} = \{ \{v_1, v_2\}; v_1, v_2 \in V \text{ and } v_1 \neq v_2 \}. $$ We define $\overline{G} = (\overline{V}, \overline{E})$ ($\overline{G}$ is the complete graph on $|\overline{V}| = \binom{n}{2}$ elements).

A matching $M$ of $G$ is said to be admissible if it induces a perfect matching $\bar{M}$ of $\bar{G}$. Let $\mathcal{M}$ denote the set of all admissible matchings of $G$. We define an equivalence class $\sim$ on $\mathcal{M}$ as follows. Given two admissible matchings $M_1, M_2 \in \mathcal{M}$, we define $M_1 \sim M_2$ if $M_2$ can be obtained from $M_1$ by replacing some of its pairings using the following operation: the operation maps a pairing $$ \{ (i_1, j_1), (i_2, j_2) \}$$ to $$ \{ (j_1, i_1), (j_2, i_2) \}.$$

There is also an action of the symmetric group $S_n$ on $\mathcal{M}$, since $S_n$ naturally acts on $[n] = \{1, \dots, n \}$ and thus it also acts on $V$.

Question: given $M_1, M_2 \in \mathcal{M}$, is there an efficient algorithm to determine whether or not there is a $\sigma \in S_n$ such that $$\sigma.M_1 \sim M_2?$$

I added the word "efficient" because of course, one can simply list all elements of $S_n$ and apply them to $M_1$ and then check whether or not $M_2$ is equivalent via $\sim$ to one of these admissible matchings.

My goal is to construct a subset $S$ of $\mathcal{M}$ such that any $M \in \mathcal{M}$ is equivalent via $\sim$ to some $M' \in S$ via some $\sigma \in S_n$ and any two distinct elements, say $M_1, M_2$ of $S$, are not related this way. In other words, there is no $\sigma \in S_n$ such that $M_2 \sim \sigma.M_1$.

In other words, I am trying to find a complete set of representatives in $\mathcal{M}$ under the equivalence relation of being related via some element of $S_n$ and $\sim$.

One thing I thought of, is to construct enough invariants of admissible matchings, under $S_n$ and $\sim$. But maybe there is a simple approach which I am failing to see.

Let $n \geq 2$ be an integer. Let \begin{align*} V &= \{(i, j); 1 \leq i, j \leq n \text{ and } i \neq j \} \\ E &= \{ \{v_1, v_2\}; v_1, v_2 \in V \text{ and } v_1 \neq v_2 \}. \end{align*} The graph $G = (V, E)$ is thus the complete graph on $|V| = n(n - 1)$ elements. Let $T$ denote the operation of interchanging $i$ and $j$. In other words, $T: V \to V$ maps $(i, j)$ to $(j, i)$. Define $\overline{V}$ to be the set of equivalence classes of $V$ under the group $\{ \operatorname{Id}, T \}$ and let $$ \overline{E} = \{ \{v_1, v_2\}; v_1, v_2 \in V \text{ and } v_1 \neq v_2 \}. $$ We define $\overline{G} = (\overline{V}, \overline{E})$ ($\overline{G}$ is the complete graph on $|\overline{V}| = \binom{n}{2}$ elements).

A matching $M$ of $G$ is said to be admissible if it induces a perfect matching $\bar{M}$ of $\bar{G}$. Let $\mathcal{M}$ denote the set of all admissible matchings of $G$. We define an equivalence class $\sim$ on $\mathcal{M}$ as follows. Given two admissible matchings $M_1, M_2 \in \mathcal{M}$, we define $M_1 \sim M_2$ if $M_2$ can be obtained from $M_1$ by replacing some of its pairings using the following operation: the operation maps a pairing $$ \{ (i_1, j_1), (i_2, j_2) \}$$ to $$ \{ (j_1, i_1), (j_2, i_2) \}.$$

There is also an action of the symmetric group $S_n$ on $\mathcal{M}$, since $S_n$ naturally acts on $[n] = \{1, \dots, n \}$ and thus it also acts on $V$.

Question: given $M_1, M_2 \in \mathcal{M}$, is there an efficient algorithm to determine whether or not there is a $\sigma \in S_n$ such that $$\sigma.M_1 \sim M_2?$$

I added the word "efficient" because of course, one can simply list all elements of $S_n$ and apply them to $M_1$ and then check whether or not $M_2$ is equivalent via $\sim$ to one of these admissible matchings.

My goal is to construct a subset $S$ of $\mathcal{M}$ such that any $M \in \mathcal{M}$ is equivalent via $\sim$ to some $M' \in S$ via some $\sigma \in S_n$ and any two distinct elements, say $M_1, M_2$ of $S$, are not related this way. In other words, there is no $\sigma \in S_n$ such that $M_2 \sim \sigma.M_1$.

In other words, I am trying to find a complete set of representatives in $\mathcal{M}$ under the equivalence relation of being related via some element of $S_n$ and $\sim$.

One thing I thought of, is to construct enough invariants of admissible matchings, under $S_n$ and $\sim$. But maybe there is a simple approach which I am failing to see.

Edit: given an admissible matching $M \in \mathcal{M}$, we can associate to it a polynomial $p_M(x_1, y_1, \dots, x_n, y_n)$ in the $2n$ variables $x_1, y_1, \dots, x_n, y_n$ of degree $d$ being the number of pairings in $M$, defined in the following way.

Given a pairing, say $\{ (i_1, j_1), (i_2, j_2) \}$ in $M$, associate to it the polynomial $$(v_{j_1} - v_{i_1}, v_{j_2} - v_{i_2}),$$ where $v_i = (x_i, y_i)^T$, for $i = 1, \dots, n$ and $(-, -)$ denotes the Euclidean inner product in $\mathbb{R}^2$.

Then form the product of the inner products associated to each pairing in $M$, and call the resulting polynomial $q_M(x_1, y_1, \dots, x_n, y_n)$. Finally, define $$ p_M(x_1, y_1, \dots, x_n, y_n) = \sum_{\sigma \in S_n} \sigma. q_M(x_1, y_1, \dots, x_n, y_n),$$ where $\sigma$ permutes the vectors $v_1 = (x_1, y_1), \dots, v_n = (x_n, y_n)$, which induces an action on the space of all polynomials in $(x_1, y_1, \dots, x_n, y_n)$.

Let $M_1, M_2 \in \mathcal{M}$. If there is some $\sigma \in S_n$ such that $M_2 \sim \sigma.M_1$, then the corresponding polynomials must be equal, i.e. $$ p_{M_1}(x_1, y_1, \dots, x_n, y_n) = p_{M_2}(x_1, y_1, \dots, x_n, y_n).$$ This is clear since, by construction, the map from $\mathcal{M}$ to $\mathbb{Z}[x_1, y_1, \dots, x_n, y_n]$ given by $$M \mapsto p_M(x_1, y_1, \dots, x_n, y_n)$$ is invariant under both the action of $S_n$ on $\mathcal{M}$ and under $\sim$.

I am not sure, but I conjecture that the converse is true, i.e. if the corresponding polynomials are equal, then there is some $\sigma \in S_n$ such that $M_2 \sim \sigma.M_1$.