17
$\begingroup$

Planar graphs have genus zero. Graphs embeddable on a torus have genus at most 1. My question is simple :

  • Are there any problems that are polynomially solvable on planar graphs but NP-hard on graphs of genus one ?

  • More generally are there any problems that are polynomially solvable on graphs of genus g but NP-hard on graphs of genus > g ?

$\endgroup$
  • $\begingroup$ For the second question, do you want the problem to be NP-hard for graphs of genus >= k, where k is a constant greater than g? OR do you just want the problem to be NP-hard for graphs whose genus isn't less than g (which is equivalent to it being NP-hard for general graphs)? $\endgroup$ – Robin Kothari Sep 3 '12 at 22:05
  • 1
    $\begingroup$ I am looking for NP-Hard problems for graphs of genus >= k, where k is a constant greater than g. $\endgroup$ – Shiva Kintali Sep 4 '12 at 6:14
16
$\begingroup$

This is publicity of my own work, but crossing number and 1-planarity are trivially solvable in planar graphs but hard for graphs of genus one. See http://arxiv.org/abs/1203.5944

$\endgroup$
  • 3
    $\begingroup$ "A graph is near-planar if it can be obtained from a planar graph by adding an edge. A graph is 1-planar if it has a drawing where every edge is crossed by at most one other edge. We show that it is NP-hard to decide whether a given near-planar graph is 1-planar." I must be missing something. Why isn't every near-planar graph also 1-planar? $\endgroup$ – Tyson Williams Sep 3 '12 at 20:27
  • 4
    $\begingroup$ What I think you're saying is that you can just take a planar embedding of $G-e$ and add the edge back in. However, that extra edge could cross more than one edge, violating 1-planarity. $\endgroup$ – Timothy Sun Sep 4 '12 at 3:36
  • $\begingroup$ @TimothySun Yes. Every edge other than $e$ will be crossed at most once (by $e$), but $e$ could be crossed by more than one other edge, which is not allowed. Thanks. $\endgroup$ – Tyson Williams Sep 4 '12 at 12:36
4
$\begingroup$

If toy problems are fine:

Let $g\in\mathbb{N}$ and let $H$ be some graph of genus $g+1$. For $\phi$ a CNF-formula, let $G_\phi$ be some encoding of $\phi$ as a planar graph plus a disjoint copy of $H$.

Given $G_\phi$, which is a graph of genus $g+1$, it is NP-hard to decide whether $\phi$ is satisfiable. This problem however becomes trivial when restricted to graphs of genus $\leq g$.

$\endgroup$
  • 2
    $\begingroup$ what is this problem on graphs of genus $\leq g$ $\endgroup$ – Sasho Nikolov Sep 5 '12 at 1:14
  • 1
    $\begingroup$ All graphs $G_\phi$ have genus $g+1$. Thus, if you restrict the problem to graphs of genus $g$, you can always reject. $\endgroup$ – Radu Curticapean Sep 5 '12 at 9:12
  • $\begingroup$ ah, it becomes really trivial, I see $\endgroup$ – Sasho Nikolov Sep 5 '12 at 16:14
2
$\begingroup$

EDIT (2012-09-05): Jeff's and Radu's comments are right. The cited result does not answer the question. To expand on Radu's comment, here is a related algorithm by Bravyi which gives an algorithm for contracting matchgate tensors on a graph $G$ with genus $g$ with run-time $T=poly(n) + 2^{2g} O(m^3)$ where $m$ is the minimum number of edges one has to remove from $G$ in order to make it planar.


Cai, Lu, and Xia recently proved the following dichotomy for #CSP counting problems:

We prove complexity dichotomy theorems in the framework of counting CSP problems. The local constraint functions take Boolean inputs, and can be arbitrary real-valued symmetric functions. We prove that, every problem in this class belongs to precisely three categories:

(1) those which are tractable (i.e., polynomial time computable) on general graphs, or
(2) those which are #P-hard on general graphs but tractable on planar graphs, or
(3) those which are #P-hard even on planar graphs.

The classication criteria are explicit.

$\endgroup$
  • 2
    $\begingroup$ This doesn't answer the question. Can category (2) can be split into (2a) tractable for planar graphs but #P-hard for toroidal graphs, and (2b) tractable for bounded-genus graphs but #P-hard for unbounded-genus graphs? $\endgroup$ – Jeffε Sep 4 '12 at 22:45
  • 3
    $\begingroup$ Case (2) consists of problems that can be reduced to counting perfect matchings in planar graphs by introducing local planar gadgets. It is also known that perfect matchings can be counted in polynomial time on bounded-genus graphs. Thus, all problems in case (2) are actually tractable on bounded-genus graphs. $\endgroup$ – Radu Curticapean Sep 4 '12 at 23:42
2
$\begingroup$

For any fixed $g$, there is a polynomial-time algorithm to determine whether a graph has genus (at most) $g$. Let $X_g$  be any problem that is NP-complete on graphs of genus greater than $g$ (e.g., 3-colourability). For each fixed $g$, the problem "Does the input graph have genus at most $g$ or is it in $X_g$ (or both)?" is NP-complete for general input but has a polynomial-time algorithm when the input is restricted to graphs of genus at most $g$.

This idea can be used quite generally to produce problems that are "hard" on general graphs but "easy" on some class $\mathcal C$ of graphs, as long as it is "easy" to determine membership in $\mathcal C$.

$\endgroup$

Your Answer

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

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