Skip to main content
MathOverflow

Return to Question

added 14 characters in body
Source Link
Turbo
Turbo
  • 13.9k
  • 1
  • 27
  • 76
  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 deterministic $O(n^{c'})$ time at some fixed $0<c'$ such that the number of perfect matchings is approximately preserved?
  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?
  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 deterministic $O(n^{c'})$ time at some fixed $0<c'$ such that the number of perfect matchings is approximately preserved?
Source Link
Turbo
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?