Problema de corte sin H

Suponga que se le da un gráfico H, simple, conectado y no dirigido.

El problema del corte sin H se define de la siguiente manera:

Dado un gráfico simple, no dirigido G, ¿hay un corte (partición de vértices en dos conjuntos no vacíos, L, R) de tal manera que los gráficos inducidos por los conjuntos de corte (L y R) no contengan un subgrafo isomorfo a H .

Por ejemplo, cuando H es el gráfico con dos vértices conectados por un solo borde, el problema es el mismo que determinar si un gráfico es bipartito y está en P.

En el caso de que H sea un triángulo, es como la versión de vértice del problema del triángulo monocromático .

Creo que he podido demostrar que cuando H está conectado a 2 con al menos tres vértices, el problema de corte sin H es NP-Completo.

No he podido encontrar ninguna referencia a este problema (y, por lo tanto, ningún resultado).

¿Podemos abandonar la condición de 2-conectividad y aún así probar NP-Completeness?

¿Alguien sabe de algún resultado conocido que implique lo anterior o un resultado más fuerte (o cree que podría ser relevante)?

Puede buscar el término "bipartición" o "partición de vértice" o "colorear" en lugar de "cortar". Se han considerado varias generalizaciones del número cromático a lo largo de las líneas que insinúa desde mediados de los años 80 (o posiblemente antes). Hay algunas referencias tempranas difíciles de encontrar en las conferencias de combinatoria canadiense, pero es posible que desee consultar Cowen, Goddard y Jesurum (JGT o SODA 1997) y referencias / citas relacionadas.

Editado el 15/02/2011

Como señalaron Aravind y Moron (en los comentarios a continuación), las siguientes referencias muestran que el problema de corte sin es NP-duro, excepto en los casos triviales.$H$

D. Achlioptas. La complejidad de la coloración libre deMatemáticas discretas. 165/166 (1997) 21-30. [pdf] .$G$

A. Farrugia. La división del vértice en propiedades hereditarias inducidas por aditivos fijos es NP-dura. Electrón. J. Combin. 11 (2004) # R46 (9 pp).

Me doy cuenta de que esto podría no responder directamente a su pregunta (sobre referencias), pero me gustaría describir un posible enfoque para mostrar la dureza NP sin la condición de 2 conectados. Faltan dos cosas: una es una prueba de la dureza NP del 'problema fuente', por así decirlo, y la otra es que estoy reduciendo a una versión 'coloreada' de H-cut que puede o Puede no ser útil. En cuanto al primer cuello de botella, creo que tengo una prueba en mi mente de que estoy siendo flojo sobre la formalización, así que espero llegar a eso pronto. Sin embargo, hasta ahora he pensado en reducir la versión coloreada a la que presentas, con poca suerte. También tengo mucha curiosidad acerca de su prueba en caso de que H esté conectado a 2, ¿podría proporcionar algunos detalles?

Entonces, la versión coloreada es la siguiente: cada vértice en el gráfico está equipado con una lista de colores de una paleta P (un conjunto fijo y finito). Estamos obligados a encontrar un corte para que ninguna partición induzca una copia monocromática de H, es decir, no hay un subconjunto de | H | vértices que inducen una copia de H, y la lista correspondiente de colores tiene una intersección no vacía.

Aquí hay una reducción de una variante restringida de d-SAT, donde d es | H |. (Tenga en cuenta que esto obviamente no funcionaría cuando d = 2).

La variante restringida de d-SAT es la siguiente:

1. Cada cláusula tiene solo literales positivos o negativos, permítanme referirme a cláusulas como las cláusulas P y N, respectivamente,

2. Cada cláusula P se puede emparejar con una cláusula N de modo que las dos cláusulas involucren el mismo conjunto de variables.

(Tengo alguna idea de por qué esta versión aparentemente restringida podría ser difícil: una restricción muy relacionada es difícil, y puedo imaginar una reducción a partir de ahí, ¡aunque podría confundirme fácilmente!)

Ante este problema, la reducción quizás se sugiera a sí misma. El gráfico tiene un vértice para cada variable de la fórmula. Para cada cláusula C_i, induzca una copia de H en el conjunto de variables que participan en la cláusula y agregue el color i a este conjunto de vértices. Esto completa la construcción.

Cualquier asignación corresponde naturalmente a un corte:

L = conjunto de todas las variables que se establecieron en 0, R = conjunto de todas las variables que se establecen en 1.

La afirmación es que una asignación satisfactoria corresponde a un corte libre de H monocromático.

En otras palabras, (L, R), cuando se da por una asignación satisfactoria, sería tal que ni L ni R induzcan una copia monocromática de H. Si L tiene tal copia, entonces observe que la cláusula P correspondiente debe haber tenido todas sus variables se establecen en 0, lo que contradice el hecho de que la asignación fue satisfactoria. Por el contrario, si R tiene dicha copia, entonces la N-cláusula correspondiente debe tener todas sus variables establecidas en 1, contradicción nuevamente.

Por el contrario, considere cualquier corte y establezca las variables de un lado a 1 y el otro a 0 (observe que no importa de qué manera lo haga, dado el tipo de fórmula con la que estamos trabajando, una asignación y se voltea las versiones son equivalentes en lo que respecta a la satisfacción). Si esta asignación no satisface una cláusula, podemos rastrearla hasta una copia monocromática de H en uno de los lados, lo que contradice la ausencia de H monocromática del corte.

La razón por la que uno tiene que permitirse la coloración es porque las copias de H pueden interferir para crear copias espurias de H que no corresponden a las cláusulas, en un intento de reducción directa. De hecho, falla, gravemente, incluso cuando H es algo tan simple como un camino.

No tuve suerte en deshacerme de los colores, y no estoy seguro de haber simplificado el problema. Sin embargo, espero que, si es correcto, pueda ser un comienzo.