patternMinor
Why is bipartite perfect matching a special case of clique problem?
Viewed 0 times
caseproblemwhyperfectcliquebipartitespecialmatching
Problem
In Lovász writes [1] :
bipartite graph has a perfect matching, which is a special case of the clique problem
Why is bipartite perfect matching a special case of clique problem?
bipartite graph has a perfect matching, which is a special case of the clique problem
Why is bipartite perfect matching a special case of clique problem?
- The Work of A.A. Razborov by L. Lovász (1990)
Solution
Let $G=(V,E)$ be the bipartite graph. Construct a new graph $G'=(V',E')$ whose vertices are the edges of $G$, and where we add $(e,e')$ to $E'$ if $e,e'$ are two edges from $G$ that don't touch each other (don't have an endpoint in common). Now there's a matching of size $s$ in $G$ if and only if there's a clique of size $s$ in $G'$. In particular, there's a perfect bipartite matching for $G$ if and only if there is a clique of size $|V|/2$ in $G'$.
Context
StackExchange Computer Science Q#50678, answer score: 6
Revisions (0)
No revisions yet.