Problemas difíciles para gráficos de mayor género

17

Las gráficas planas tienen género cero. Los gráficos que se pueden insertar en un toro tienen un género como máximo 1. Mi pregunta es simple:

¿Hay algún problema que sea polinomialmente solucionable en gráficos planos pero NP-duro en gráficos del género uno?
En términos más generales, ¿hay algún problema que pueda resolverse polinómicamente en gráficos del género g pero NP-duro en gráficos del género> g?

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

Para la segunda pregunta, ¿desea que el problema sea NP difícil para los gráficos de género> = k, donde k es una constante mayor que g? ¿O simplemente quiere que el problema sea NP-hard para gráficos cuyo género no sea menor que g (que es equivalente a NP-hard para gráficos generales)?

Robin Kothari

1

Estoy buscando problemas NP-Hard para gráficos de género> = k, donde k es una constante mayor que g.

Shiva Kintali

16

Esto es publicidad de mi propio trabajo, pero el número de cruce y la 1-planaridad son trivialmente solucionables en gráficos planos pero difíciles para los gráficos del género uno. Ver http://arxiv.org/abs/1203.5944

alguien
fuente

3

"Un gráfico es casi plano si se puede obtener de un gráfico plano agregando un borde. Un gráfico es 1 plano si tiene un dibujo en el que cada borde se cruza como máximo con otro borde. Mostramos que es NP -Difícil decidir si un gráfico casi plano plano dado es 1 plano. Debo estar perdiendo algo. ¿Por qué no todos los gráficos casi planos también son 1 planos?

Tyson Williams

44

Lo que creo que está diciendo es que puede tomar una incrustación plana de

y agregar el borde nuevamente. Sin embargo, ese borde adicional podría cruzar más de un borde, violando la 1-planaridad.

G - e

$G-e$

Timothy Sun

@TimothySun Sí. Cada borde que no sea

se cruzará como máximo una vez (por

), pero

podría cruzarse por más de otro borde, lo que no está permitido. Gracias.

e

$e$

e

$e$

e

$e$

Tyson Williams

4

Si los problemas con los juguetes están bien:

Deje y sea una gráfica del género . Para una CNF-fórmula, deja que sea un poco de codificación de como un gráfico planar además una copia disjuntos de . $g\in\mathbb{N}$ $H$ $g+1$ $\phi$ $G_\phi$ $\phi$ $H$

Dado , que es un gráfico del género , es NP-difícil decidir si es satisfactoria. Sin embargo, este problema se vuelve trivial cuando se restringe a gráficos de género . $G_\phi$ $g+1$ $\phi$ $\leq g$

Radu Curticapean
fuente

2

¿Cuál es este problema en los gráficos del género

\leq g

$\leq g$

Sasho Nikolov

1

Todos los gráficos

tienen el género

. Por lo tanto, si restringe el problema a gráficos del género

, siempre puede rechazar.

G_{ϕ}

$G_\phi$

g + 1

$g+1$

g

$g$

Radu Curticapean

ah, se vuelve realmente trivial, ya veo

Sasho Nikolov

2

EDITAR (2012-09-05): Los comentarios de Jeff y Radu son correctos. El resultado citado no responde la pregunta. Para ampliar el comentario de Radu, aquí hay un algoritmo relacionado de Bravyi que proporciona un algoritmo para contraer tensores de compuerta en un gráfico con género con tiempo de ejecución donde es el número mínimo de aristas que uno tiene que quitar de para hacerlo plano. $G$ $g$ $T=poly(n) + 2^{2g} O(m^3)$ $m$ $G$

Cai, Lu y Xia probaron recientemente la siguiente dicotomía para problemas de conteo #CSP:

Probamos teoremas de dicotomía de complejidad en el marco de contar problemas de CSP. Las funciones de restricción locales toman entradas booleanas y pueden ser funciones simétricas arbitrarias de valor real. Probamos que cada problema en esta clase pertenece precisamente a tres categorías:

(1) aquellos que son manejables (es decir, tiempo polinomial computable) en gráficos generales, o
(2) aquellos que son # P-hard en gráficos generales pero manejables en gráficos planos , o
(3) aquellos que son # P-hard incluso en gráficas planas.

Los criterios de clasificación son explícitos.

Martin Schwarz
fuente

2

Esto no responde la pregunta. ¿Se puede dividir la categoría (2) en (2a) manejable para gráficos planos pero # P-hard para gráficos toroidales y (2b) manejable para gráficos de género acotado pero # P-hard para gráficos de género ilimitado?

Jeffε

3

El caso (2) consiste en problemas que pueden reducirse a contar coincidencias perfectas en gráficos planos mediante la introducción de dispositivos planos locales. También se sabe que los emparejamientos perfectos se pueden contar en tiempo polinómico en gráficos de género acotado. Por lo tanto, todos los problemas en el caso (2) son realmente manejables en gráficos de género acotado.

Radu Curticapean

2

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

$\mathcal C$ $\mathcal C$

David Richerby
fuente

Problemas difíciles para gráficos de mayor género

Respuestas: