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 ?

Improve this question
$\endgroup$
2
  • $\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, 2012 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, 2012 at 6:14

4 Answers 4

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

Improve this answer
$\endgroup$
3
  • 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, 2012 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, 2012 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, 2012 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$.

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ what is this problem on graphs of genus $\leq g$ $\endgroup$
    – Sasho Nikolov
    Sep 5, 2012 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, 2012 at 9:12
  • $\begingroup$ ah, it becomes really trivial, I see $\endgroup$
    – Sasho Nikolov
    Sep 5, 2012 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.

Improve this answer
$\endgroup$
2
  • 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, 2012 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, 2012 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$.

Improve this answer
$\endgroup$

Your Answer

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

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