4
$\begingroup$

In some problems related to the Ising model in physics and mathematics the following problem comes up:

Suppose I have a graph $G$. Then an even spanning subgraph of $G$ is a subgraph where you keep all the vertices and some of the edges such that each vertex has even degree.There is always at least one since the empty spanning subgraph is always even. Now, among all the even spanning subgraphs of $G$ I want to sample one uniformly at random.

Is there an fast and preferably easy to implement algoritm to do that?

Is this a well studied problem? If yes: could you point me to some references?

Some background: The space of even spanning subgraphs of a graph has some nice structure since if you have two of them then you can take their symmetric difference and it will still be an even spanning subgraph. This means that it is a vector space of the field $\mathbb{F}_2$ and you can pick a basis of that space - in particular this shows that the number of even spanning subgraphs is always a power of 2. I wonder how difficult it is to find the basis elements since if you have some you just flip coins for each and take the symmetric difference of all the graphs where you get head. Another point is that there might be a smart low-tech randomized way to do this.

$\endgroup$
  • 2
    $\begingroup$ An even subgraph is usually known as a 2-factor. $\endgroup$ – Yuval Filmus Jun 19 at 11:56
1
$\begingroup$

Based on this answer from Math.SE you can construct a simple algorithm for uniformly sampling an even spanning subgraph.

Assume without loss of generality that $G$ is connected (otherwise you can apply the sampling algorithm to each connected component and return the union). Let us denote $G$'s vertices by $v_1,...,v_n$, and given $i>1$ let $P_i$ be some simple path from $v_1$ to $v_i$ (such path exists since $G$ is connected).

Given $A\subseteq\{2,..,n\}$ and some spanning subgraph $H$, define $H^A$ to be the graph obtained from $H$ by flipping the edges in each $P_i$ for $i\in A$, i.e. if $H$ is represented by $x_H\in\mathbb{F}_2^{|E|}$, and $P_2,...,P_n$ are represented by $x_2,...,x_n\in \mathbb{F}_2^{|E|}$, then $H^A=x_H\oplus\left(\bigoplus\limits_{i\in A} x_i\right)$. Note that for $A\neq B$ we have $H^A\neq H^B$. $H^A=H^B$ for some $A\neq B$ iff there exists nonempty $A\subseteq\{2,...,n-1\}$ such that $\bigoplus\limits_{i\in A}x_i=0$ (i.e. the vectors $x_i$ are dependent). Suppose $i\in A$, and let $G_A$ denote the spanning graph represented by $\bigoplus\limits_{j\in A}P_i$. Flipping the edges of any path $P_j$ only changes the parity of the degrees of $v_1$ and $v_j$. Thus, as $G_A$ is obtained by starting with the empty graph and flipping the edges of every $P_j$ with $j\in A$, $deg_{G_A}(v_i)$ is odd, which means $G_A$ is not the empty graph.

Now we can define the following equivalence relation on subgraphs of $G$, $H_1\sim H_2\iff\exists A\subseteq\{2,..,n\}:H_2=H_1^A$. Based on the previous observation, each equivalence class contains $2^{n-1}$ different elements.

The second key observation is that each equivalence class contains a unique even subgraph of $G$. Given a subgraph $H$, for any vertex $v_{i>2}$ with odd $deg_H(v_i)$ flip the edges in $P_i$. This only changes the parity of the degrees of $v_1,v_i$ in $H$. Proceed in this manner until $deg_H(v_2),...,deg_H(v_n)$ are all even. Since the sum of the degrees is always even, $deg_H(v_1)$ must now be even too, which means that the newly obtained equivalent graph $H'$ is an even spanning subgraph. For uniqueness, suppose for the purpose of contradiction that $H\sim H'$ are two different equivalent even spanning subgraphs of $G$, i.e. $H'=H^A$ for some non empty $A\subseteq\{2,..,n\}$. Let $i\in A$ be some path index in $A$, then clearly $deg_{H'}(v_i)$ is odd, since $deg_{H}(v_i)$ is even and its parity is only changed while flipping the edges of $P_i$.

This was covered in the linked answered by Yly. Now you have a simple sampling algorithm that requires $O(|V|+|E|)$ preprocessing time. Execute BFS from $v_1$ to obtain the paths $P_2,...,P_n$. Sample uniformly a spanning subgraph $H$, now for each $v_i$ with odd $deg_H(v_i)$ flip the edges of $P_i$. In this manner you find the unique even spanning subgraph in $[H]$, using $O(n^2)$ time. Uniformity follows from the fact that all equivalence classes have the same size, and each contains a unique even spanning subgraph.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.