¿Propiedad de gráfico NP-completo que es hereditaria, pero no aditiva?

Una propiedad de gráfico se denomina hereditaria si se cierra con respecto a la eliminación de vértices (es decir, todas las subgrafías inducidas heredan la propiedad). Una propiedad gráfica se llama aditiva si se cierra con respecto a tomar uniones disjuntas.

No es difícil encontrar propiedades que sean hereditarias, pero no aditivas. Dos ejemplos simples:

$\;\;\;$ (1) El gráfico está completo.

$\;\;\;$ (2) El gráfico no contiene dos ciclos vértice-disjuntos.

En estos casos, es obvio que la propiedad es heredada por subgrafos inducidos, pero tomando dos gráficos disjuntos que tienen la propiedad, su unión puede no preservarla.

Los dos ejemplos anteriores son propiedades decimables polytime (aunque para (2) es algo menos trivial). Si queremos propiedades más duras, aún podrían crearse siguiendo el patrón de (2), pero reemplazando los ciclos con tipos de gráficos más complicados. Entonces, sin embargo, podemos encontrarnos fácilmente con la situación en la que el problema ni siquiera permanece en , bajo supuestos de complejidad estándar, como . Parece menos trivial encontrar un ejemplo que se mantenga dentro de , pero aún es difícil. $NP$ $NP\neq coNP$ $NP$

Pregunta: ¿Conoce una propiedad gráfica (preferiblemente natural) de que sea hereditaria, pero no aditiva? $NP$

cc.complexity-theory graph-theory graph-algorithms np Andras Farago
fuente

Ahora ha formulado una serie de preguntas sobre las propiedades "naturales". Puede ser útil comprender cuál es la motivación para algunas de estas preguntas.

Suresh Venkat

@Suresh Me gustaría comprender mejor qué hace que un problema sea natural, en lugar de artificial, artificial. Creo que el concepto de naturalidad es un puente importante entre la teoría y la realidad, y vale la pena explorarlo. Lo que encuentro intrigante es que, aunque no tenemos una definición formal de qué problemas son "naturales", las personas generalmente tienen un consenso claro sobre si un problema específico es natural o no. Quizás publique una pregunta por separado sobre este tema, para obtener más información sobre cómo lo ven los demás.

Andras Farago

Respuestas:

Creo que el problema de la cubierta -clique, que pregunta si existe una partición de los vértices en los conjuntos manera que cada conjunto induzca una camarilla, tiene las propiedades deseadas. $k$ $k$

Claramente, tomar subgrafías inducidas no puede aumentar el tamaño mínimo de dicha partición. Por otro lado, cuando tomas la unión disjunta de dos gráficos, debes tomar la unión de la partición en camarillas de cada uno.

Vinicius dos Santos
fuente

De manera similar, la cubierta de vértices / conjunto dominante de tamaño a lo sumo

funciona de manera similar.

k

$k$

Pero ambos problemas que mencionaste son polinomios para

fijo , ¿verdad? Creo que si obliga a

a formar parte de la entrada, deja de ser una propiedad bien definida en el sentido de la pregunta formulada.

k

$k$

k

$k$

Vinicius dos Santos

-clique propiedad cubierta, como se indica en la respuesta, no es

. Un gráfico puede tener una partición

en camarillas, pero un subgrafo no puede heredar esta propiedad. Esto sigue siendo cierto tanto para

constante como variable .

k

$k$

h e r e d i t a r y

$hereditary$

k

$k$

k

$k$

Andras Farago

Esto se puede resolver fácilmente permitiendo particiones vacías (si el problema original no lo permite, solo considere esta versión modificada). En lugar de "cubierta de camarilla de tamaño

", considere "como máximo de tamaño

k

$k$

k

$k$

Vinicius dos Santos

Sí, creo, ¡con esta modificación ahora es una respuesta correcta! Si arreglamos

, entonces la propiedad es equivalente a "¿es el complemento de G 3 coloreable?" (lo que significa que el complemento puede ser coloreado por un máximo de 3 colores). Esto es hereditario, y de hecho es NP completo, por la integridad NP conocida de la capacidad de coloración del gráfico 3. La propiedad tampoco es aditiva, porque si

tienen sus complementos individualmente en 3 colores, el complemento de su unión disjunta puede no permanecer en 3 colores (puede requerir hasta 6 colores).

k = 3

$k=3$

G_{1}

$G_1$

G_{2}

$G_2$

Andras Farago

Considera este problema

$G$ $P$ $Q$

Sigue siendo NP completo incluso si las propiedades son hereditarias.

Ahora, claramente, una solución del problema anterior para un gráfico también proporciona una solución para los subgrafos inducidos. Pero al tomar la unión de gráficos de la misma familia que G podría no resolverse usando esa solución.

Por ejemplo, la partición de gráficos generales en gráficos de intervalo de unidades disjuntas es NP completa pero al tomar la unión de todos los bordes posibles (completar el gráfico) resuelve el problema trivialmente.

Dibyayan
fuente

Tenga en cuenta que la pregunta busca una propiedad que no sea aditiva. En su ejemplo, nada parece garantizar que deben existir dos gráficos que tengan la propiedad, pero su unión disjunta no.

Andras Farago

$G = (V,E)$ $C_1,\ldots,C_m$ $C_i$ $V$ $E$ $C_i$ . Conjeturo lo siguiente:

$k \geq 3$ $G$ $k$ ,

$k = 2$ , el problema es polinomial: esto debería seguir a partir de "Códigos Gauss, Gráficos Hamiltonianos Planos y Permutaciones Clasificables por Pila" de Rosenstiehl y Tarjan.

Si (1) es verdadero, entonces debería responder a su pregunta, ya que le da una propiedad que es hereditaria, pero claramente no es aditiva.

(NOTA AGREGADA: la conjetura (2) es diferente de la "conjetura de la cubierta del ciclo doble" de Szekeres y Seymour, a pesar de la homonimidad).

Súper 8
fuente

Esta propiedad no es hereditaria. La eliminación de un vértice puede aumentar el número de ciclos necesarios para cubrir todos los bordes, porque el vértice eliminado puede eliminar un ciclo que se utilizó para cubrir muchos bordes. El ejemplo más simple es cuando todo el gráfico es solo un ciclo. La eliminación de un vértice hace que cualquier ciclo sea imposible, ya que no quedan ciclos.

Andras Farago

G

$G$

G

$G$

v

$v$

v

$v$

k

$k$