Problemas difíceis para gráficos de gênero mais altos

17

Gráficos planares têm gênero zero. Os gráficos incorporados em um toro têm gênero no máximo 1. Minha pergunta é simples:

Existem problemas que são polinomialmente solucionáveis em gráficos planares, mas que são rígidos em NP em gráficos do gênero um?
De um modo mais geral, existem problemas polinomialmente solucionáveis em gráficos do gênero g, mas que são rígidos em NP em gráficos do gênero g?

cc.complexity-theory ds.algorithms graph-theory planar-graphs Shiva Kintali
fonte

Para a segunda pergunta, você deseja que o problema seja NP-difícil para gráficos do gênero> = k, onde k é uma constante maior que g? OU você quer que o problema seja NP-difícil para gráficos cujo gênero não é menor que g (o que equivale a ser NP-difícil para gráficos gerais)?

Robin Kothari

11

Estou procurando problemas NP-Hard para gráficos do gênero> = k, onde k é uma constante maior que g.

Shiva Kintali 4/12/12

16

Isso é publicidade do meu próprio trabalho, mas o número de cruzamento e a planaridade 1 são trivialmente solucionáveis em gráficos planares, mas difíceis para gráficos do gênero um. Veja http://arxiv.org/abs/1203.5944

alguém
fonte

3

"Um gráfico é quase plano se pode ser obtido a partir de um gráfico plano adicionando uma aresta. Um gráfico é 1 planar se houver um desenho em que cada aresta seja atravessada por no máximo uma outra aresta. Mostramos que é NP - difícil decidir se um dado gráfico próximo ao plano é 1-plano. " Eu devo estar esquecendo alguma coisa. Por que todo gráfico quase plano também não é 1 plano?

Tyson Williams

4

O que eu acho que você está dizendo é que você pode simplesmente incluir uma incorporação plana de

e adicionar a aresta novamente. No entanto, essa aresta extra pode cruzar mais de uma aresta, violando a planaridade 1.

G - e

$G-e$

Timothy Sun

@TimothySun Sim. Cada borda que não seja

será cruzada no máximo uma vez (por

), mas

poderá ser cruzada por mais de uma outra borda, o que não é permitido. Obrigado.

e

$e$

e

$e$

e

$e$

Tyson Williams

4

Se os problemas com brinquedos forem bons:

Seja e seja um gráfico do gênero . Para um CNF-fórmula, deixar ser alguns codificação de como um gráfico planar mais uma cópia disjuntos de . $g\in\mathbb{N}$ $H$ $g+1$ $\phi$ $G_\phi$ $\phi$ $H$

Dado , que é um gráfico do gênero , é NP difícil decidir se é satisfatório. Esse problema, no entanto, se torna trivial quando restrito a gráficos do gênero . $G_\phi$ $g+1$ $\phi$ $\leq g$

Radu Curticapean
fonte

2

o que é esse problema em gráficos de gênero

\leq g

$\leq g$

Sasho Nikolov

11

Todos os gráficos

têm o gênero

. Assim, se você restringir o problema aos gráficos do gênero

, poderá sempre rejeitar.

G_{ϕ}

$G_\phi$

g + 1

$g+1$

g

$g$

Radu Curticapean

ah, torna-se realmente trivial, eu vejo

Sasho Nikolov

2

EDIT (05-09-2012): Os comentários de Jeff e Radu estão certos. O resultado citado não responde à pergunta. Para expandir o comentário de Radu, aqui está um algoritmo relacionado de Bravyi, que fornece um algoritmo para a contratação de tensores de caixa de fósforo em um gráfico com o gênero com tempo de execução onde é o número mínimo de arestas que é necessário remover de para torná-lo plano. $G$ $g$ $T=poly(n) + 2^{2g} O(m^3)$ $m$ $G$

Cai, Lu e Xia recentemente provaram a seguinte dicotomia para problemas de contagem de #CSP:

Nós provamos teoremas de dicotomia de complexidade na estrutura de contagem de problemas de CSP. As funções de restrição local recebem entradas booleanas e podem ser funções simétricas arbitrárias com valor real. Provamos que todos os problemas desta classe pertencem exatamente a três categorias:

(1) aqueles que são tratáveis (isto é, computáveis em tempo polinomial) em gráficos gerais, ou
(2) aqueles que são # P-rígidos em gráficos gerais, mas são tratáveis em gráficos planares , ou
(3) aqueles que são # P-rígidos mesmo em gráficos planares.

Os critérios de classificação são explícitos.

Martin Schwarz
fonte

2

Isso não responde à pergunta. A categoria (2) pode ser dividida em (2a) tratável para gráficos planares, mas # P-difícil para gráficos toroidais e (2b) tratável para gráficos de gênero limitado, mas # P-difícil para gráficos de gênero ilimitado?

Jeffε

3

O caso (2) consiste em problemas que podem ser reduzidos à contagem de correspondências perfeitas em gráficos planares através da introdução de dispositivos planares locais. Sabe-se também que combinações perfeitas podem ser contadas em tempo polinomial em gráficos de gênero limitado. Assim, todos os problemas no caso (2) são realmente tratáveis em gráficos de gênero limitado.

Radu Curticapean

2

$g$ $g$ $X_g$ $g$ $g$ $g$ $X_g$ $g$

$\mathcal C$ $\mathcal C$

David Richerby
fonte

Problemas difíceis para gráficos de gênero mais altos

Respostas: