Problema de camarilla en gráficos fijos

21

Como sabemos, la función -clique toma un subgrafo ( abarcando ) de un gráfico -vertex completo , y genera sif contiene una -clique . Las variables en este caso corresponden a los bordes de . Se sabe (Razborov, Alon-Boppana) que, para , esta función requiere circuitos monótonos de tamaño aproximadamente . C L I Q U E ( n , k ) G K n n K n 1 G k K n 3 k n / 2 n kkCLIQUE(n,k)GKnnKn1GkKn3kn/2nk

Pero, ¿qué si tomamos un gráfico fijo , y consideramos la función booleana monótona , que toma un subconjunto de vértices, y genera si algunos vértices en forman un Clique en . Las variables en este caso corresponden a los vértices de , y la función es sólo la función clique estándar, pero restringido a los que abarcan subgraphs de uno fijo gráfico . C L I Q U E ( G , k ) S [ n ] 1 k S G K n GGKnCLIQUE(G,k)S[n]1kSGKnG

1. ¿Existen gráficos de vértices para los cuales requiere circuitos monótonos de tamaño mayor que ? Supongo que no. G C L I Q U E ( G , k ) n O ( log n )nGCLIQUE(G,k)nO(logn)
2. ¿Es un problema NP-hard para alguna secuencia de gráficos ? Supongo que no. ( G n : n = 1 , 2 ... )CLIQUE(Gn,k)(Gn:n=1,2)

Tenga en cuenta que si son todas las camarillas máximas en , entonces puede calcularse como un OR de umbral- funciones, la -ésima prueba si . Por lo tanto, si , entonces todo el circuito es de tamaño polinómico. Pero, ¿qué pasa con los gráficos con un número exponencial de camarillas máximas? (Una camarilla es máxima si no se le puede agregar ningún vértice). G C L I Q U E ( G , k ) r k i | S aC i | k r = p o l y ( n )C1,,CrGCLIQUE(G,k)rki|SaCi|kr=poly(n)

Es posible "incrustar" en para un gráfico particular en vértices. En particular, Bollobas y Thomason (1981) han demostrado que, si es un gráfico de Hadamard cuyos vértices son subconjuntos de , y dos vértices y son adyacentes si fes par, entonces contiene una copia isomórfica de cada gráfico en vértices. ¿Se puede combinar este hecho con el límite inferior de Razborov (de aproximadamente ) para para concluir que C L I Q U E ( H , k ) H n = 2 m H [ m ] u v | u v | H G m m k C L I Q U E ( m , k ) C L I Q U E (CLIQUE(m,k)CLIQUE(H,k)Hn=2mH[m]uv|uv|HGmmkCLIQUE(m,k)m k H m k ( k - 1 ) k kCLIQUE(H,k) requiere circuitos monótonos de tamaño aproximadamente ? Un problema potencial aquí es que, aunque el gráfico "contiene" todos los gráficos de vértex , estos gráficos no están en el mismo conjunto de vértices. Y el argumento de Razborov exige que las entradas positivas y negativas ( cliques y complementos de gráficos completos -partitos) son gráficos en el mismo conjunto de vértices. Además, todas las entradas positivas ( -cliques) son solo copias isomórficas de una misma -clique fija .mkH mk(k1)k k

3. ¿ Alguna idea? ¿Alguien ha visto este tipo de problemas siendo considerado? Quiero decir, problemas de decisión para subgrafos de un grafo fijo . ¿O, digamos, el problema SAT para sub-CNF de un CNF fijo (satisfactorio) (obtenido al eliminar algunos literales)?

Motivación: problemas de este tipo están relacionados con la complejidad de los algoritmos de optimización combinatoria. Pero parecen ser interesantes en sí mismos. ¿Por qué deberíamos buscar algoritmos que sean eficientes en todos los gráficos? En realidad, generalmente estamos interesados ​​en las propiedades de piezas pequeñas de un gráfico (grande) (red de calles en un país, o facebook, o similares).

Observación 1: Si la gráfica es bipartita , entonces la matriz de incidencia del borde del vértice de las desigualdades para todos es totalmente unimodular , y uno puede resolver el problema de la camarilla en subgrafías inducidas de mediante programación lineal. Por lo tanto, para los gráficos bipartitos , tiene un circuito pequeño (aunque no monótono). x u + x v1 ( u , v ) E G G C L I Q U E ( G , k )G=(LR,E)xu+xv1(u,v)EGGCLIQUE(G,k)

Observación 2: Una indicación de que, en el caso de los gráficos bipartitos , la respuesta a la pregunta 1 "debería" ser NO es que el siguiente juego monótono de Karchmer-Wigderson en solo necesita bits de comunicación. Deje que sea mayor número de vértices en un subgrafo bipartito completo de . Alice obtiene un conjunto de nodos rojos, Bob un conjunto de nodos azules de modo que . El objetivo es encontrar un no-borde entre y .G O ( log n ) k G A B | A | + | B | > k A BGGO(logn)kGAB|A|+|B|>kAB

Stasys
fuente
más pensamientos (1) parece que podría obtener un resultado similar al definir una función de "filtro" que tiene el mismo número de variables que los bordes y los bordes "filtros" del gráfico fijo en función de los valores 0/1 de las variables booleanas ... .? Esto podría disminuir un poco el análisis debido a la construcción del gráfico inducido que se mueve de los bordes a los vértices. (2) una pregunta clave más simple está incrustada en su pregunta que solo vale la pena abordar. ¿Cuáles son algunos gráficos con camarillas máximas exponenciales? el ejemplo de hadamard puede no ser suficiente porque es muy "grande".
vzn
estaba buscando algo vagamente similar recientemente y me encontré con este interesante hecho: "Una descomposición de camarilla codiciosa de un gráfico se obtiene eliminando las camarillas máximas de un gráfico una por una hasta que el gráfico esté vacío. Recientemente hemos demostrado que cualquier descomposición de camarilla codiciosa de un gráfico de orden tiene al mostn n 2 / 4 camarillas ". --mcguinnessnn2/4
vzn
@vzn: a tu última pregunta. Hay una construcción simple (no recuerdo de quién). Tome copias de "anti-trianges" de vértice disjuntos (triples de vértices sin bordes entre ellos), y coloque bordes entre todos los vértices de cualquiera de los dos anti-tringles. El número de camarillas máximas es entonces 2 n / 3 , y esto es óptimo (ya no es posible). n/32n/3
Stasys
@vzn: sobre el resultado de McGuinness. Como entendí, él descompone todos los bordes en un pequeño número de camarillas máximas (tamaño) desunidas de borde. Pero puede suceder que la camarilla máxima del subgrafo inducido no se encuentre en ninguno de ellos. Aún así, el resultado parece estar en la "dirección correcta".
Stasys
Sobre el comentario 2 : cuando dices buscar una camarilla en un bipartito, ¿te refieres a un bipartito completo?
MassimoLauria el

Respuestas:

10

GkknΩ(k)

Puede encontrar la Complejidad parametrizada en papel de los procedimientos de búsqueda DPLL en este enlace .

MassimoLauria
fuente
1
Un muy buen resultado! En realidad, mi pregunta surgió al intentar mostrar el mismo resultado para las refutaciones de plano de corte (CP) en forma de árbol para el problema (camarilla). Para las derivaciones en forma de árbol tenemos dos (¿solo?) Herramientas: (1) argumentos de complejidad de comunicación y (2) juegos Player-Delayer de Pudlak e Impagliazzo. El comentario 2 implica que (1) fallará (probablemente) para el problema de Clique. ¿Existe alguna analogía de (2) en el caso de las pruebas de CP?
Stasys
6

Creo que este documento puede responder a sus preguntas: http://arxiv.org/abs/1204.6484

El documento define familias de problemas NP 3SAT difíciles, de modo que la estructura de la fórmula se fija para cada n, y la entrada es la polaridad de la fórmula.

Usando la reducción estándar de 3SAT a CLIQUE (cada cláusula 3CNF define un conjunto de 8 asignaciones posibles (o 7 asignaciones satisfactorias), con bordes entre asignaciones no conflictivas), hay un gráfico tal que después de eliminar un vértice para cada cláusula, es NP difícil de encontrar la camarilla máxima (o incluso para aproximarse a su tamaño, utilizando productos gráficos o productos gráficos aleatorizados)

usuario15669
fuente
2

En el tercer trimestre, hay un trabajo empírico sobre la "columna vertebral" y las posibles "puertas traseras" de los problemas del SAT. la columna vertebral es el conjunto de literales que son verdaderos en cada tarea satisfactoria. Una puerta trasera en un problema SAT es un conjunto (con suerte pequeño) de variables que proporcionan un "atajo" para resolver el problema. estas dos estructuras probablemente serían útiles y / o clave para comprender lo que usted denomina "sub-CNF" o CNF con algunas variables eliminadas. pero también DP, el algoritmo de davis putnam puede verse como una exploración sistemática de muchos "sub-CNF" del CNF para resolverlo.

[1] Backbones y Backdoors en Satisfiability por Kilby et al.

vzn
fuente
SS