¿Hay algún problema en

16

Estoy buscando un problema que pertenece a en gráficos generales pero está en en gráficos de ancho de árbol acotado. De hecho, creo que estos problemas son más difíciles que usar la programación dinámica normal en acotado -Gráficos de árbol de ancho para resolverlos.Σ2PP

Saeed
fuente
Si el problema está en P para los gráficos de ancho de árbol acotado, ¿por qué dice que es "más difícil que usar DP normal" en dichos gráficos?
Suresh Venkat

Respuestas:

11

List Chromatic Number (¿Es cierto que el gráfico tiene un color de vértice cada vez que cada vértice obtiene una lista de k colores admisibles?) Es un problema -completo, pero solucionable en tiempo lineal en gráficos de ancho de árbol acotado:Π2PAG

http://www.ii.uib.no/~daniello/papers/EqColoring.pdf

Daniel Marx
fuente
3
Si le gusta este resultado, tal vez también esté probado en el siguiente documento: arxiv.org/abs/1110.4077 . Apareció en el arXiv esta semana, y los autores muestran que List Edge Chromatic Number y List Total Chromatic Number también se pueden resolver en tiempo lineal para gráficos de ancho de árbol acotado.
Bart Jansen
13

Creo que 2-clique-coloring [GT19 en Schaefer y Umans ] es un ejemplo. La pregunta es si el gráfico dado puede ser (incorrectamente) de 2 colores de tal manera que ninguna de sus camarillas máximas sea monocromática. Para los gráficos de ancho de árbol acotado, cada camarilla máxima debe aparecer dentro de una bolsa única de la descomposición del árbol, por lo que debería funcionar utilizar el enfoque de programación dinámica estándar en el que los estados del programa dinámico son 2 colores de la bolsa que colorean correctamente todos camarillas máximas dentro de la bolsa y son consistentes con el buen estado de las bolsas para niños.

David Eppstein
fuente
1
También está en P para TW (<= k) por esta razón: el color k-clique es expresable en MS: "Existe X_1, ... X_k (Partición (X_1, ..., X_k) y ForAll X (CliqueMax (X) => no (Existe X_i (Forall x en X (x en X_i)))))
M. kanté
2
X1,,Xk:(IsPartition(X1,,Xk)X:(MaxClique(X)¬(Xi:xX:xXi)))