PROBLEMA DE CAMARILLA , CONTINUACIÓN I
Clases especiales de gráficos [ editar ]
Los gráficos planos y otras familias de gráficos dispersos se han discutido anteriormente: tienen linealmente muchas camarillas máximas, de tamaño acotado, que se pueden enumerar en tiempo lineal. [20] En particular, para gráficos planos, cualquier camarilla puede tener como máximo cuatro vértices, según el teorema de Kuratowski . [23]
Los gráficos perfectos se definen por las propiedades de que su número de camarilla es igual a su número cromático , y que esta igualdad se mantiene también en cada una de sus subgrafías inducidas . Para gráficos perfectos, es posible encontrar una camarilla máxima en tiempo polinómico, utilizando un algoritmo basado en programación semidefinida . [45] Sin embargo, este método es complejo y no combinatorio, y se han desarrollado algoritmos especializados de búsqueda de camarillas para muchas subclases de gráficos perfectos. [46] En los gráficos de complemento de grafos bipartitos , el teorema de König permite el problema máximo camarilla a ser resuelto usando técnicas de coincidencia. En otra clase de gráficos perfectos, los gráficos de permutación , una camarilla máxima es una subsecuencia decreciente más larga de la permutación que define el gráfico y se puede encontrar usando algoritmos conocidos para el problema de subsecuencia decreciente más largo. Por el contrario, cada instancia del problema de subsecuencia decreciente más largo se puede describir de manera equivalente como un problema de encontrar una camarilla máxima en un gráfico de permutación. [47] Incluso, Pnueli y Lempel (1972) proporcionan un algoritmo de tiempo cuadrático alternativo para las camarillas máximas en los gráficos de comparabilidad , una clase más amplia de gráficos perfectos que incluye los gráficos de permutación como un caso especial. [48] En gráficos cordales, las camarillas máximas se pueden encontrar enumerando los vértices en un orden de eliminación y comprobando los vecindarios de camarillas de cada vértice en este orden. [49]
En algunos casos, estos algoritmos también pueden extenderse a otras clases de gráficos no perfectos. Por ejemplo, en un gráfico circular , el vecindario de cada vértice es un gráfico de permutación, por lo que se puede encontrar una camarilla máxima en un gráfico circular aplicando el algoritmo del gráfico de permutación a cada vecindario. [50] De manera similar, en un gráfico de unidad de disco (con una representación geométrica conocida), existe un algoritmo de tiempo polinómico para camarillas máximas basado en la aplicación del algoritmo para complementos de gráficos bipartitos en vecindades compartidas de pares de vértices. [51]
Karp (1976) sugirió el problema algorítmico de encontrar una camarilla máxima en un gráfico aleatorio extraído del modelo Erdős-Rényi (en el que cada borde aparece con probabilidad 1/2 , independientemente de los otros bordes ) . Debido a que la camarilla máxima en un gráfico aleatorio tiene un tamaño logarítmico con alta probabilidad, se puede encontrar mediante una búsqueda de fuerza bruta en el tiempo esperado 2 O (log 2 n ) . Este es un límite de tiempo cuasi polinomial . [52] Aunque el número de camarillas de tales gráficos generalmente es muy cercano a 2 log 2 n , algoritmos codiciosos simplesasí como las técnicas de aproximación aleatoria más sofisticadas solo encuentran camarillas con un tamaño de log 2 n , la mitad de grande. El número de camarillas máximas en tales gráficos es con exponencial de alta probabilidad en log 2 n , lo que impide que los métodos que enumeran todas las camarillas máximas se ejecuten en tiempo polinómico. [53] Debido a la dificultad de este problema, varios autores han investigado el problema de la camarilla plantada , el problema de la camarilla en gráficos aleatorios que se han aumentado mediante la adición de grandes camarillas. [54] Mientras que los métodos espectrales [55] y la programación semidefinida [56] pueden detectar camarillas ocultas de tamañoΩ ( √ n ) , actualmente no se conocen algoritmos de tiempo polinómico para detectar aquellos de tamaño o ( √ n ) (expresados usando la notación little-o ). [57]
Algoritmos de aproximación [ editar ]
Varios autores han considerado algoritmos de aproximación que intentan encontrar una camarilla o conjunto independiente que, aunque no es el máximo, tiene un tamaño tan cercano al máximo como se puede encontrar en el tiempo polinómico. Aunque gran parte de este trabajo se ha centrado en conjuntos independientes en gráficos dispersos, un caso que no tiene sentido para el problema de la camarilla complementaria, también se ha trabajado en algoritmos de aproximación que no utilizan tales supuestos de escasez. [58]
Feige (2004) describe un algoritmo de tiempo polinómico que encuentra una camarilla de tamaño Ω ((log n / log log n ) 2 ) en cualquier gráfico que tenga un número de camarilla Ω ( n / log k n ) para cualquier constante k . Mediante el uso de este algoritmo cuando el número clique de un gráfico de entrada dado es de entre n / log n y n / log 3 n , el cambio a un algoritmo diferente de Boppana y Halldórsson (1992) para los gráficos con los números camarilla más altas, y la elección de una de dos camarilla de vértices si ambos algoritmos no logran encontrar algo, Feigeproporciona un algoritmo de aproximación que encuentra una camarilla con varios vértices dentro de un factor de O ( n (log log n ) 2 / log 3 n ) del máximo. Aunque la relación de aproximación de este algoritmo es débil, es la más conocida hasta la fecha. [59] Los resultados sobre la dureza de la aproximación descritos a continuación sugieren que no puede haber un algoritmo de aproximación con una relación de aproximación significativamente menor que la lineal.
Límites inferiores [ editar ]
NP-completitud [ editar ]
El problema de decisión de la camarilla es NP-completo . Fue uno de los 21 problemas originales de Richard Karp mostrados como NP completos en su artículo de 1972 "Reducibilidad entre problemas combinatorios". [61] Este problema también se mencionó en el artículo de Stephen Cook que presenta la teoría de los problemas NP-completos. [62] Debido a la dureza del problema de decisión, el problema de encontrar una camarilla máxima también es NP-duro. Si uno pudiera resolverlo, también podría resolver el problema de decisión, comparando el tamaño de la camarilla máxima con el parámetro de tamaño dado como entrada en el problema de decisión.
La prueba de completitud NP de Karp es una reducción de muchos del problema de satisfacción booleana . Describe cómo traducir fórmulas booleanas en forma conjuntiva normal (CNF) en instancias equivalentes del problema de la camarilla máxima. [63] La satisfacción, a su vez, se demostró NP-completa en el teorema de Cook-Levin . A partir de una fórmula CNF dada, Karp forma un gráfico que tiene un vértice para cada par ( v , c ) , donde v es una variable o su negación y c es una cláusula en la fórmula que contiene v. Dos de estos vértices están conectados por un borde si representan asignaciones de variables compatibles para diferentes cláusulas. Es decir, hay una ventaja de ( v , c ) a ( u , d ) cada vez que c ≠ d y u y v no son negaciones mutuas. Si k denota el número de cláusulas en la fórmula CNF, entonces las camarillas k- vértice en este gráfico representan formas consistentes de asignar valores de verdad a algunas de sus variables para satisfacer la fórmula. Por lo tanto, la fórmula es satisfactoria si y solo si k-vertex camarilla existe. [61]
Algunos problemas de NP completo (como el problema del vendedor ambulante en gráficos planos ) pueden resolverse en un tiempo que es exponencial en una función sublineal del parámetro de tamaño de entrada n , significativamente más rápido que una búsqueda de fuerza bruta. [64] Sin embargo, es poco probable que tal límite de tiempo subexponencial sea posible para el problema de la camarilla en gráficos arbitrarios, ya que implicaría límites subexponenciales similares para muchos otros problemas estándar de NP completo. [sesenta y cinco]
Complejidad del circuito [ editar ]
La dificultad computacional del problema de la camarilla lo ha llevado a probar varios límites inferiores en la complejidad del circuito . La existencia de una camarilla de un tamaño dado es una propiedad de gráfico monótono , lo que significa que, si existe una camarilla en un gráfico dado, existirá en cualquier superógrafo . Debido a que esta propiedad es monótona, debe existir un circuito monótono, que use solo puertas y / o puertas , para resolver el problema de decisión de la camarilla para un tamaño de camarilla fijo determinado. Sin embargo, se puede demostrar que el tamaño de estos circuitos es una función superpolinómica del número de vértices y el tamaño de la camarilla, exponencial en la raíz cúbica del número de vértices. [66] Incluso si un pequeño número deNO se permiten puertas , la complejidad sigue siendo superpolinómica. [67] Además, la profundidad de un circuito monótono para el problema de la camarilla utilizando puertas de abanico acotado debe ser al menos un polinomio en el tamaño de la camarilla. [68]
Complejidad del árbol de decisiones [ editar ]
La complejidad del árbol de decisión (determinista) de determinar una propiedad gráfica es el número de preguntas de la forma "¿Hay un borde entre el vértice u y el vértice v ? eso tiene que ser respondido en el peor de los casos para determinar si un gráfico tiene una propiedad particular. Es decir, es la altura mínima de un árbol de decisión booleano para el problema. Hay n ( n - 1) / 2 posibles preguntas que hacer. Por lo tanto, cualquier propiedad gráfica puede determinarse como máximo con n ( n - 1) / 2preguntas También es posible definir la complejidad del árbol de decisión aleatorio y cuántico de una propiedad, el número esperado de preguntas (para el peor de los casos) que un algoritmo aleatorio o cuántico necesita haber respondido para determinar correctamente si el gráfico dado tiene la propiedad . [69]
Debido a que la propiedad de contener una camarilla es monótona, está cubierta por la conjetura de Aanderaa-Karp-Rosenberg , que establece que la complejidad del árbol de decisión determinista de determinar cualquier propiedad de gráfico monótono no trivial es exactamente n ( n - 1) / 2 . Para las propiedades de gráficos monótonos arbitrarios, esta conjetura permanece sin probar. Sin embargo, para los árboles de decisión deterministas, y para cualquier k en el rango de 2 ≤ k ≤ n , la propiedad de contener un k -clique ha demostrado tener la complejidad del árbol de decisión exactamente n ( n - 1) / 2 por Bollobás (1976). Los árboles de decisión deterministas también requieren un tamaño exponencial para detectar camarillas, o un gran tamaño polinómico para detectar camarillas de tamaño limitado. [70]
La conjetura de Aanderaa-Karp-Rosenberg también establece que la complejidad del árbol de decisión aleatorio de las funciones monótonas no triviales es Θ ( n 2 ) . La conjetura nuevamente no se ha comprobado, pero se ha resuelto por la propiedad de contener una camarilla k para 2 ≤ k ≤ n . Se sabe que esta propiedad tiene una complejidad de árbol de decisión aleatoria Θ ( n 2 ) . [71] Para los árboles de decisión cuántica, el límite inferior más conocido es Ω ( n ) , pero no se conoce un algoritmo de coincidencia para el caso de k ≥ 3 . [72]
Intratabilidad de parámetros fijos [ editar ]
La complejidad parametrizada es el estudio teórico de la complejidad de problemas que están equipados naturalmente con un pequeño parámetro entero k y para los cuales el problema se vuelve más difícil a medida que k aumenta, como encontrar k- cliques en los gráficos. Se dice que un problema es manejable con parámetros fijos si hay un algoritmo para resolverlo en entradas de tamaño n , y una función f , de modo que el algoritmo se ejecute en el tiempo f ( k ) n O (1) . Es decir, es manejable con parámetros fijos si se puede resolver en tiempo polinómico para cualquier valor fijo de ky además si el exponente del polinomio no depende de k . [73]
Para encontrar camarillas k -vertex, el algoritmo de búsqueda de fuerza bruta tiene un tiempo de ejecución O ( n k k 2 ) . Debido a que el exponente de n depende de k , este algoritmo no es manejable con parámetros fijos. Aunque puede mejorarse mediante una multiplicación de matriz rápida, el tiempo de ejecución todavía tiene un exponente que es lineal en k Por lo tanto, aunque el tiempo de ejecución de los algoritmos conocidos para el problema de la camarilla es polinomial para cualquier k fijo, estos algoritmos no son suficientes para la trazabilidad de parámetros fijos . Downey y compañeros (1995)definió una jerarquía de problemas parametrizados, la jerarquía W, que conjeturaron que no tenían algoritmos manejables de parámetros fijos. Probaron que un conjunto independiente (o, de manera equivalente, una camarilla) es difícil para el primer nivel de esta jerarquía, W [1] . Por lo tanto, según su conjetura, la camarilla no tiene un algoritmo manejable de parámetros fijos. Además, este resultado proporciona la base para las pruebas de la dureza W [1] de muchos otros problemas y, por lo tanto, sirve como un análogo del teorema de Cook-Levin para la complejidad parametrizada. [74]
Chen y col. (2006) mostraron que la búsqueda de camarillas k- vértice no se puede hacer en el tiempo n o ( k ) a menos que falle la hipótesis del tiempo exponencial . Nuevamente, esto proporciona evidencia de que no es posible un algoritmo manejable de parámetro fijo. [75]
Aunque los problemas de enumerar camarillas máximas o encontrar camarillas máximas es poco probable que sean manejables con parámetros fijos con el parámetro k , pueden ser manejables con parámetros fijos para otros parámetros de complejidad de instancia. Por ejemplo, se sabe que ambos problemas son manejables con parámetros fijos cuando se parametrizan por la degeneración del gráfico de entrada. [35]
Dureza de aproximación [ editar ]
Los resultados débiles insinúan que el problema de la camarilla podría ser difícil de aproximar se conoce desde hace mucho tiempo. Garey y Johnson (1978) observaron que, debido al hecho de que el número de camarilla toma valores enteros pequeños y es NP-difícil de calcular, no puede tener un esquema de aproximación de tiempo completamente polinomial . Si hubiera disponible una aproximación demasiado precisa, redondear su valor a un entero daría el número exacto de camarilla. Sin embargo, se sabía poco más hasta principios de la década de 1990, cuando varios autores comenzaron a establecer conexiones entre la aproximación de las camarillas máximas y las pruebas probabilísticamente comprobables . Utilizaron estas conexiones para demostrar la dureza de los resultados de aproximación para el problema de la camarilla máxima. [76] Después de muchas mejoras en estos resultados, ahora se sabe que, para cada número real ε > 0 , no puede haber un algoritmo de tiempo polinómico que se aproxime a la camarilla máxima dentro de un factor mejor que O ( n 1 - ε ) , a menos que P = NP . [77]
La idea aproximada de estos resultados de inaplicabilidad es formar un gráfico que represente un sistema de prueba probabilísticamente verificable para un problema de NP completo, como el problema de satisfacción booleana. En un sistema de prueba probabilísticamente verificable, una prueba se representa como una secuencia de bits. Una instancia del problema de satisfacción debe tener una prueba válida si y solo si es satisfactoria. La prueba se verifica mediante un algoritmo que, después de un cálculo de tiempo polinómico en la entrada al problema de satisfacción, elige examinar un pequeño número de posiciones elegidas al azar de la cadena de prueba. Dependiendo de qué valores se encuentren en esa muestra de bits, el verificador aceptará o rechazará la prueba, sin mirar el resto de los bits. No se permiten falsos negativos: siempre se debe aceptar una prueba válida. Sin embargo, una prueba inválida a veces puede ser aceptada por error. Para cada prueba inválida, la probabilidad de que el verificador la acepte debe ser baja.[78]
Para transformar un sistema de prueba probabilísticamente verificable de este tipo en un problema de camarilla, se forma un gráfico con un vértice para cada posible ejecución de aceptación del verificador de prueba. Es decir, un vértice se define por una de las posibles elecciones aleatorias de conjuntos de posiciones para examinar, y por valores de bit para aquellas posiciones que harían que el verificador acepte la prueba. Dos vértices son adyacentes, en este gráfico, si las dos corridas de aceptación correspondientes ven los mismos valores de bit en cada posición que ambos examinan. Cada cadena de prueba (válida o no válida) corresponde a una camarilla, el conjunto de corridas de aceptación que ven esa cadena de prueba, y todas las camarillas máximas surgen de esta manera. Una de estas camarillas es grande si y solo si corresponde a una cadena de prueba que aceptan muchos verificadores de pruebas. Si la instancia de satisfacción original es satisfactoria, tendrá una cadena de prueba válida, una que sea aceptada por todas las ejecuciones del verificador, y esta cadena corresponderá a una camarilla grande en el gráfico. Sin embargo, si la instancia original no es satisfactoria, entonces todas las cadenas de prueba no son válidas, cada cadena de prueba tiene solo un pequeño número de ejecuciones de verificación que la aceptan por error, y todas las camarillas son pequeñas. Por lo tanto, si se pudiera distinguir en el tiempo polinómico entre gráficos que tienen grandes camarillas y gráficos en los que todas las camarillas son pequeñas, o si se pudiera aproximar con precisión el problema de la camarilla, aplicar esta aproximación a los gráficos generados a partir de instancias de satisfacción permitiría instancias satisfactorias para distinguirse de instancias insatisfactorias. Sin embargo, esto no es posible a menos que P = NP. y esta cadena corresponderá a una camarilla grande en el gráfico. Sin embargo, si la instancia original no es satisfactoria, entonces todas las cadenas de prueba no son válidas, cada cadena de prueba tiene solo un pequeño número de ejecuciones de verificación que la aceptan por error, y todas las camarillas son pequeñas. Por lo tanto, si se pudiera distinguir en el tiempo polinómico entre gráficos que tienen grandes camarillas y gráficos en los que todas las camarillas son pequeñas, o si se pudiera aproximar con precisión el problema de la camarilla, aplicar esta aproximación a los gráficos generados a partir de instancias de satisfacción permitiría instancias satisfactorias para distinguirse de instancias insatisfactorias. Sin embargo, esto no es posible a menos que P = NP. y esta cadena corresponderá a una camarilla grande en el gráfico. Sin embargo, si la instancia original no es satisfactoria, entonces todas las cadenas de prueba no son válidas, cada cadena de prueba tiene solo un pequeño número de ejecuciones de verificación que la aceptan por error, y todas las camarillas son pequeñas. Por lo tanto, si se pudiera distinguir en el tiempo polinómico entre gráficos que tienen grandes camarillas y gráficos en los que todas las camarillas son pequeñas, o si se pudiera aproximar con precisión el problema de la camarilla, aplicar esta aproximación a los gráficos generados a partir de instancias de satisfacción permitiría instancias satisfactorias para distinguirse de instancias insatisfactorias. Sin embargo, esto no es posible a menos que P = NP. cada cadena de prueba tiene solo un pequeño número de ejecuciones de corrector que lo aceptan por error, y todas las camarillas son pequeñas. Por lo tanto, si se pudiera distinguir en el tiempo polinómico entre gráficos que tienen grandes camarillas y gráficos en los que todas las camarillas son pequeñas, o si se pudiera aproximar con precisión el problema de la camarilla, aplicar esta aproximación a los gráficos generados a partir de instancias de satisfacción permitiría instancias satisfactorias para distinguirse de instancias insatisfactorias. Sin embargo, esto no es posible a menos que P = NP. cada cadena de prueba tiene solo un pequeño número de ejecuciones de corrector que lo aceptan por error, y todas las camarillas son pequeñas. Por lo tanto, si se pudiera distinguir en el tiempo polinómico entre gráficos que tienen grandes camarillas y gráficos en los que todas las camarillas son pequeñas, o si se pudiera aproximar con precisión el problema de la camarilla, aplicar esta aproximación a los gráficos generados a partir de instancias de satisfacción permitiría instancias satisfactorias para distinguirse de instancias insatisfactorias. Sin embargo, esto no es posible a menos que P = NP. luego, aplicar esta aproximación a los gráficos generados a partir de instancias de satisfacción permitiría distinguir instancias satisfactorias de instancias insatisfactorias. Sin embargo, esto no es posible a menos que P = NP. luego, aplicar esta aproximación a los gráficos generados a partir de instancias de satisfacción permitiría distinguir instancias satisfactorias de instancias insatisfactorias. Sin embargo, esto no es posible a menos que P = NP.
No hay comentarios:
Publicar un comentario