1
$\begingroup$

I'm stuck on some of the theory in these notes, i'm trying to learn about randomized algorithms in general and am currently stuck on some notes regarding perfect matchings.

Here is a link to the notes http://www.cs.berkeley.edu/~sinclair/cs271/n2.pdf and my question concerns the material from the isolating lemma (on the penultimate page excluding references) to the end.

Ok so i'll try and explain what i understand to perhaps highlight exactly what i don't understand. In general we have a bipartite graph $G$ which we know has a perfect matching, we use this algorithm to find a perfect matching. I'd also like to highlight if at any point i use the term matching i mean perfect matching.

So i am fine with the isolating lemma which states

$\textbf{Lemma}$-Let $S_{1},...,S_{k}$ be subsets of a set $S$ of cardinality $m$. Let each element $x \in S$ have a weight $w_{x}$ chosen independently and uniformly at random from the set $\{0,1,...,2m-1\}.$ Then $$\mathrm{Pr}(\exists\; \mathrm{a\;unique\;set\;of\;minimum\;weight})\geq \frac{1}{2}.$$

This lemma is used in the following context for bipartite matchings which i am also fine with. Given a bipartite graph the set $S=E$, where $E$ is the edge set of $G$. Then $S_{1},...,S_{k}$ are the matchings of $G$ and each edge $(ij) \in E$ is assigned a weight $w_{ij}$ in $\{0,1,...,2|E|-1\}$ independently and uniformly at random. The weight $w(M)$ of a matching $M$ is simply the sum of all the weights of it's edges.

The matrix $B$ is the matrix central to the whole algorithm which is obtained as follows. Replace every entry of the Tutte matrix which is $x_{ij}$ with $2^{w_{ij}}$. Recall the Tutte matrix is obtained form the $n\times n$ bipartite graph by placing $x_{ij}$ in entry $a_{ij}$ if edge $(ij) \in E$ and placing $0$ otherwise.

So here is the algorithm which outputs a perfect matching provided we have a unique minimum weight matching, if no such matching exists it fails.

$\textbf{Algorithm}$:Calculate $2^{w}$ the largest power of $2$ to divide $det(B)$

for each edge $(i,j)$ in parallel do

compute $t_{ij}=det(B_{ij})\frac{2^{w_{ij}}}{2^{w}}$ where $B_{ij}$ is the $(i,j)$ minor of $B$, place $(i,j)$ in $M$ iff $t_{ij}$ is an odd integer.

If $M$ is a perfect matching then output $M$ else output fail.

$\textbf{EndAlgorithm}$

Ok so here is the main claim and the proof of which is the source of my problems :)

$\textbf{Claim}$: If the minimum weight perfect matching is unique then the above algorithm outputes it.

i will give a rough outline of the proof as it is in the attachment

$\textbf{Proof}$: It says that if $M_{0}$ is the minimum weight matching then it's weight is the $w$ we calculated, the reason for this is that

$det(B)=\sum_{M \in \mathcal{M}(G)} \pm 2^{w(M)}$ where $\mathcal{M}(G)$ is the set of all matchings. This is easy to see and in addition $det(B)/2^{w}$ is odd.

It then says for an edge $(i,j)$, $B_{ij}$ corresponds to the perfcect matchings in $G\setminus \{ij\}$.

It then claims that $t_{ij}$ is odd if and only if $(i,j)$ is an edge of $M_{0}$. It states $det(B_{ij})=\sum_{M \in \mathcal{M}(G \setminus \{i,j\})} \pm 2^{w(M)}$

which they say is equal to (which i'm not sure is correct because of no $\pm $)

$ 2^{-w_{ij}} \sum_{M \cup \{i,j\} \in \mathcal{M}(G)} 2^{w (M \cup \{i,j\})}$

firstly what does ${M \cup \{i,j\} \in \mathcal{M}(G)}$ mean? If we already have a perfect matching how can we add the edge $\{i,j\}$ and still obtain a perfect matching?Is this a notational mistake on their behalf?

Secondly i dont undertstand how $t_{ij}$ is odd if $\{i,j\} \in M_{0}$? This is because surely $det(B_{ij})/2^{w}$ is even as by removing $\{i,j\}$ from $G$ surely we have removed $M_{0}$ and so the weight of every matching in $G \setminus\{i,j\}$ is larger than $w$ and so $t_{ij}=2^{w_{ij}}det(B_{ij})/2^{w}$ is even? I'd really appreciate any help in clarifying this, thanks.

$\endgroup$
1
$\begingroup$

For the first question:

The summation $2^{-w_{ij}}∑_{M∪\{i,j\}∈M(G)}2^{w(M∪\{i,j\})}$ is not running over perfect matchings $M$, but instead think of arbitrary edge set $M$ which satisfies $M∪\{i,j\}∈M(G)$. In other words, the summation is over all edge sets obtained from perfect matchings containing $ij$ by removing $ij$.

The second question may confused you because of the first problem. The matching $M_0 - ij$ is still there, contributing to the summation so that the result is odd. Your reasoning is somehow correct except that you still have $M_0 - ij$.

$\endgroup$
  • $\begingroup$ Ok i think i realised this yesterday. By $G\setminus \{i,j\}$ they are removing the vertices $i$ and $j$ and not the edge $(i,j)$ right? this would make sense as they are removing the $i$th row and $j$th column, to obtain the co factor matrix $B_{ij}$. Which then would essentially be the weights of all the edges not including vertices $i$ and $j$. So infact they are looking at all perfect matchings in the graph obtained by removing one vertex from each vertex class? $\endgroup$ – Pavan Sangha Jan 30 '15 at 9:37
  • $\begingroup$ If you are talking about your formula for $\det (B_{ij})$, then that's right. The idea is basically in the determinant expansion of the Tutte matrix, collecting the nonzero summands containing the indeterminate $x_{ij}$. $\endgroup$ – Seok Jan 31 '15 at 2:16

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.