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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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

Improve this answer
$\endgroup$
1
  • $\begingroup$ I guess the basic reference is Thomassen's paper "The graph genus problem is NP-complete." MR1022112 $\endgroup$
    – François G. Dorais
    Commented Jul 17, 2011 at 4:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .