¿Se ha estudiado la complejidad del siguiente problema?
Entrada : un gráfico cúbico (o regular) , un límite superior naturalG = ( V , E ) t
Pregunta : ¿hay una partición de en partes de tamaño modo que la suma de los órdenes de los subgrafos correspondientes (no necesariamente conectados) sea como máximo ?| E | / 3 3 t
Trabajo relacionado Encontré bastantes artículos en la literatura que demuestran las condiciones necesarias y / o suficientes para la existencia de una partición en algunos gráficos que contienen tres bordes, que de alguna manera están relacionados, y algunos otros sobre cuestiones de complejidad computacional de problemas que se cruzan con el anterior (p. ej., la partición debe producir subgrafos isomorfos a o , y no se asocia ningún peso con una partición dada), pero ninguno de ellos se ocupó exactamente del problema anterior. P 4
Enumerar todos esos documentos aquí sería un poco tedioso, pero la mayoría de ellos citan o son citados por Dor y Tarsi .
20101024: Encontré este artículo de Goldschmidt et al. , quienes prueban que el problema de la división de aristas en un gráfico en partes que contienen AL MÁXIMO aristas, de tal manera que la suma de los órdenes de los subgrafos inducidos es como máximo , es NP completo, incluso cuando . ¿Es obvio que el problema sigue siendo NP-completo en gráficos cúbicos, cuando requerimos igualdad estricta wrt ?t k = 3 k
Información Adicional
He intentado algunas estrategias que fallaron. Más precisamente, encontré algunos contraejemplos que prueban que:
maximizar el número de triángulos no conduce a una solución óptima; que de alguna manera me parece contra-intuitivo, ya que los triángulos son aquellos subgrafos con el orden más bajo entre todos los gráficos posibles en tres bordes;
particionar el gráfico en componentes conectados tampoco necesariamente conduce a una solución óptima. La razón por la que parecía prometedor puede ser menos obvia, pero en muchos casos se puede ver que intercambiar bordes para conectar un subgrafo dado conduce a una solución con un peso menor (ejemplo: intente eso en un triángulo con un borde adicional conectado a cada uno vértice; el triángulo es una parte, el resto es una segunda, con un peso total de 3 + 6 = 9. Luego, el intercambio de dos bordes da un camino y una estrella, con un peso total de 4 + 4 = 8.
fuente
Respuestas:
Aquí hay una sugerencia sobre cómo demostrar que es NP difícil. No sé si esto funciona o no. Primero, considere el mismo problema en multigraphs. La dureza NP puede ser más fácil de probar allí. Intente reducir desde el MAX CUT cúbico, que es NP difícil incluso de aproximar (Berman y Karpinski "en algunos resultados de inaproximabilidad más estrictos"). Divide cada borde en dos y en cada uno de los nuevos vértices de grado 2 adjunta un vértice con bucle automático. ¿Su partición máxima corresponde a un corte máximo?
-
Aquí hay un poco más de explicación.
(1) El problema de maximizar (número de fuentes + número de sumideros) sobre todas las orientaciones de un gráfico cúbico está relacionado con MAXCUT mediante alguna función lineal. Esto requiere mostrar cierta potencia central entre los cortes máximos y las orientaciones máximas de fuentes y sumideros. En una dirección, en un corte máximo (U, V), podemos orientar todos los bordes de U a V. Los bordes internos E (U) forman una coincidencia, por lo que estos pueden orientarse de manera arbitraria y similar para E (V), y El número total de fuentes y sumideros es una función lineal del tamaño del corte. En la otra dirección, dada una orientación máxima de fuentes y sumideros, la partición U = vértices de grado 0 o 1, V = vértices de grado 2 o 3 da un corte.
(2) En la transformación de bisección de bordes que describí anteriormente, en una configuración óptima, cada bucle tiene el mismo color que el borde al lado, y wlog ese borde tiene el mismo color que el otro borde (sin bucle) al lado ese. Por lo tanto, cada borde bisecado tiene un color proveniente de su bucle adjunto y otro color. Esto corresponde a una orientación y se aplica (1).
fuente