P132: Enumeration of all minimal blocker in a bipartite graph

P132: Enumeration of all minimal blocker in a bipartite graph

Input:

A bipartite graph $G = (U, V, E)$.

Output:

All minimal blocker in $G$.

Complexity:

Polynomial delay and space.

Comment:

A \textit{blocker} of $G$ is an edge subset $X$ of $E$ such that $G' = (U, V, E \setminus X)$ has no perfect matching.

Reference:

[Boros2006] (Bibtex)