2
$\begingroup$

Let $B_{n,n}$ be a bipartite graph on $2n$ vertices with $n$ vertices of each color.

Given two integers $g$ and $M$, construct the smallest genus $g$ $B_{n,n}$ with exactly $M$ matchings.

My first question is whether for a genus $g$ and matching number $M$, is there a way to quickly check such a bipartite graph on $2n$ vertices exists? My second question is whether there is an algorithm to construct such a graph quickly if such a graph exists?

$\endgroup$

1 Answer 1

2
$\begingroup$

The graph genus problem is NP-hard, so I don't know if this can really be done, at least we don't expect anything to be done quickly.

http://en.wikipedia.org/wiki/Graph_embedding#Computational_complexity

$\endgroup$
1
  • $\begingroup$ I guess the basic reference is Thomassen's paper "The graph genus problem is NP-complete." MR1022112 $\endgroup$ Jul 17, 2011 at 4:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.