Skip to main content
1 of 2
Turbo
  • 13.9k
  • 1
  • 27
  • 76

Graph to Bipartite conversion preserving number of perfect matchings

  1. Given a graph $G$ on $n$ vertices is there a technique to convert to a balanced bipartite graph $B$ with $O(n^c)$ vertices at some fixed $0<c$ in $O(n^{c'})$ time at some fixed $0<c'$ such that the number of perfect matchings is preserved?

If 1. is unknown then

  1. Given a graph $G$ on $n$ vertices is there a technique to convert to a balanced bipartite graph $B$ with $O(n^c)$ vertices at some fixed $0<c$ in $O(n^{c'})$ time at some fixed $0<c'$ such that the number of perfect matchings is approximately preserved?
Turbo
  • 13.9k
  • 1
  • 27
  • 76