HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Why is bipartite perfect matching a special case of clique problem?

Submitted by: @import:stackexchange-cs··
0
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?

  • 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.