11
$\begingroup$

What is currently known about the approximability of the genus problem? A preliminary search tells me that a constant factor approximation is trivial for sufficiently dense graphs, and an $n^\epsilon$-approximation algorithm has been ruled out. Is this information up-to-date, or are there better bounds known?

$\endgroup$
8
$\begingroup$

The best published results all appear in a 1997 paper by Jianer Chen, Saroja P. Kanchi, and Arkady Kanevsky.

  • For any fixed $\varepsilon>0$, computing the genus of a graph with additive error $O(n^\varepsilon)$ is NP-hard.

  • There is a trivial linear-time algorithm to embed any $n$-vertex graph of (unknown) genus $g$ on an orientable surface of genus $\max\{4g, g+4n\}$: Assign an arbitrary cyclic order to the edges leaving each vertex (keeping loops and parallel edges together). In other words, when the genus is large, every embedding is a good approximation of the best embedding.

  • There is a polynomial-time $O(\sqrt{n})$-approximation algorithm for bounded-degree graphs.

It is an open question whether there is an efficient constant-factor approximation algorithm.

$\endgroup$
2
  • 2
    $\begingroup$ I don't understand how it follows from [Chen, Kanchi, Kanevsky '97] that computing the genus with the multiplicative approximation of $O(n^{\varepsilon})$ is NP-hard. E.g. computing the MAX CUT with an additive approximation $O(n^{\varepsilon})$ is also NP-hard, but the algorithm of Goemans and Williamson gives 0.878... approximation. $\endgroup$ – Yury Oct 11 '12 at 3:01
  • $\begingroup$ Yes, you're right. I've updated my answer in light of yours. $\endgroup$ – Jeffε Oct 13 '12 at 1:38
5
$\begingroup$

I wanted to add to JɛffE's comprehensive answer that to the best of my knowledge there are no lower bounds on the approximation factor for this problem. As far as we know, there can be an approximation algorithm that always gives a constant factor approximation (even if the genus is very small).

The paper Chen, Kanchi, and Kanevsky [CKK '97] only says that computing the genus with additive error $O(n^{1-\varepsilon})$ is NP-hard. Here is a very informal outline of their argument. It will be clear that this argument cannot be used to prove a lower bound on the approximation factor. Consider a graph $G$ such that it is NP-hard to determine whether $\mathrm{genus}(G) \leq g^*$ or $\mathrm{genus}(G) \geq g^*+1$ (for some $g^*$); such a graph exists since the problem is NP-hard. Let $n$ be the number of vertices in $G$. Let $k$ be a large constant. Take $N = n^k$ disjoint copies of the graph $G$ and consider their union. Then in the obtained graph $G'$, it is NP-hard to determine whether $\mathrm{genus}(G') \leq N g^*$ or $\mathrm{genus}(G') \geq N(g^*+1)$. That is, it is NP-hard to compute $\mathrm{genus}(G')$ with additive error $N = (Nn)^{k/{k+1}} = |V(G')|^{k/{k+1}} = |V(G')|^{1-\varepsilon}$, where $\varepsilon = 1/(k+1)$. This construction does not give us any lower bound on the approximation factor; the ratio of $N(g^*+1)$ to $Ng^*$ equals the ratio of $g^*+1$ to $g^*$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy