Problema de clique em gráficos fixos

Como sabemos, a função -clique pega um subgrafo ( estendendo-se ) de um gráfico -vertex completo , e gera se contém um -clique . As variáveis ​​nesse caso correspondem às arestas de . Sabe-se (Razborov, Alon-Boppana) que, para , essa função requer circuitos monotônicos de tamanho em torno de . C L I Q U E ( n , k ) G ⊆ K n n K n 1 G k K n 3 ≤ k ≤ n / 2 n $k$$CLIQUE(n,k)$$G\subseteq K_n$$n$$K_n$$1$$G$$k$$K_n$$3\leq k\leq n/2$$n^k$

Mas e se pegarmos um gráfico fixo e considerarmos a função booleana monótona , que pega um subconjunto de vértices e gera se alguns vértices em formam um Grupo Fechado em . Variáveis neste caso, correspondem a vértices de , e a função é apenas a função facção padrão, mas restrito para os que medem subgráficos de um fixo gráfico . C L I Q U E ( G , k ) S ⊆ [ n ] 1 k S G K n$G\subseteq K_n$$CLIQUE(G,k)$$S\subseteq [n]$$1$$k$$S$$G$$K_n$$G$

1. Existem gráficos vértices para os quais requer circuitos monotônicos de tamanho maior que ? Eu acho que não. G C L I Q U E ( G , k ) n O ( log n $n$$G$$CLIQUE(G,k)$$n^{O(\log n)}$

2. Is um problema NP-difícil para alguns sequência de gráficos ? Eu acho que não. ( G n : n = 1 , 2 … $CLIQUE(G_n,k)$$(G_n\colon n=1,2\ldots)$

Observe que se são todos os cliques máximos em , então pode ser computado como um OR de threshold- , cujo teste se . Assim, se , todo o circuito é de tamanho polinomial. Mas e os gráficos com um número exponencial de cliques máximos? (Um clique é máximo, nenhum vértice pode ser adicionado a ele.) G C L I Q U E ( G , k ) r k i | S a ∩ C i | ≥ k r = p o l y ( n $C_1,\ldots,C_r$$G$$CLIQUE(G,k)$$r$$k$$i$$|S_a\cap C_i|\geq k$$r=poly(n)$

É possível "incorporar" o no para um gráfico específico em vértices. Em particular, Bollobas e Thomason (1981) mostraram que, se é um gráfico de Hadamard cujos vértices são subconjuntos de , e dois vértices e são adjacentes iffé par, então contém uma cópia isomórfica de todo gráfico em vértices. Esse fato pode ser combinado com o limite inferior de Razborov (de cerca de ) para concluir que C L I Q U E ( H , k ) H n = 2 $CLIQUE(m,k)$$CLIQUE(H,k)$$H$$n=2^m$[ m ] u v | u ∩ v | H G m m k C L I Q U E ( m , k ) C L I Q U E ( H , k $H$$[m]$$u$$v$$|u\cap v|$$H$$G$$m$$m^k$$CLIQUE(m,k)$$CLIQUE(H,k)$ requer circuitos monótonos de tamanho sobre ? Um problema em potencial aqui é que, embora o gráfico "contenha" todos os gráficos -vertex, esses gráficos não estão no mesmo conjunto de vértices. E o argumento de Razborov exige que entradas positivas e negativas ( cliques- e complementos de gráficos completos de partita ) sejam gráficos no mesmo conjunto de vértices. Além disso, todas as entradas positivas ( -cliques) são apenas cópias isomórficas de uma e a mesma -clique fixa .$m^k$$H$ $m$( k - 1 $k$$(k-1)$$k$ $k$

3. Alguma idéia? Alguém viu esse tipo de problema sendo considerado? Quero dizer, problemas de decisão para subgráficos de um gráfico fixo . Ou, digamos, o problema SAT para sub-CNFs de um CNF fixo (satisfatório) (obtido pela remoção de alguns literais)?

Motivação: problemas desse tipo estão relacionados à complexidade dos algoritmos de otimização combinatória. Mas eles parecem ser interessantes em si mesmos. Por que devemos procurar algoritmos que sejam eficientes em todos os gráficos? Na realidade, geralmente estamos interessados ​​nas propriedades de pequenos pedaços de um gráfico (grande) (rede de ruas de um país, ou facebook, ou similares).

Observação 1: Se o gráfico for bipartido , a matriz de incidência da borda do vértice das desigualdades para todos é totalmente unodimensional , e pode-se resolver o problema de clique em subgráficos induzidos de via programação linear. Assim, para gráficos bipartidos , possui um circuito pequeno (embora não monótono). x u + x v ≤ $G=(L\cup R,E)$$x_u+x_v\leq 1$G G C L I Q U E ( G , k $(u,v)\not\in E$$G$$G$$CLIQUE(G,k)$

Observação 2: Uma indicação de que, no caso dos gráficos bipartidos , a resposta à pergunta 1 "deveria" de fato ser NÃO é que o seguinte jogo monótono de Karchmer-Wigderson no precisa apenas de bits de comunicação. Vamos ser o maior número de vértices em um subgrafo bipartite completo . Alice obtém um conjunto de nós vermelhos, Bob um conjunto de nós azuis, de modo que . O objectivo é encontrar uma não-aresta entre e .G O ( log n ) k G A B | Um | + | B | > k A $G$$G$$O(\log n)$$k$$G$$A$$B$$|A|+|B|>k$$A$$B$

Fizemos uma pesquisa sobre o problema de provar em resolução semelhante a uma árvore se um gráfico fixo tem um clique do tamanho (onde é geralmente pequeno). Em particular, descobrimos que refutações de tamanho são necessárias para uma grande classe de gráficos.k k n Ω ( k $G$$k$$k$$n^{\Omega(k)}$

Você pode encontrar o artigo Complexidade parametrizada dos procedimentos de pesquisa DPLL neste link .

Acredito que este documento possa responder às suas perguntas: http://arxiv.org/abs/1204.6484

O artigo define famílias de problemas difíceis de NP 3SAT, de modo que a estrutura da fórmula é fixa para cada n, e a entrada é a polaridade da fórmula.

Usando a redução padrão de 3SAT para CLIQUE (cada cláusula 3CNF define um conjunto de 8 atribuições possíveis (ou 7 atribuições satisfatórias), com arestas entre atribuições não conflitantes), existe um gráfico que, após remover um vértice para cada cláusula, é NP difícil encontrar a camarilha máxima (ou até aproximar seu tamanho, usando produtos gráficos ou produtos gráficos aleatórios)

No terceiro trimestre, há algum trabalho empírico sobre o "backbone" e possíveis "backdoors" dos problemas do SAT. o backbone é o conjunto de literais que são verdadeiros em todas as atribuições satisfatórias. Um backdoor para um problema SAT é um conjunto (possivelmente pequeno) de variáveis ​​que fornecem um "atalho" para resolver o problema. essas duas estruturas provavelmente seriam úteis e / ou essenciais para entender o que você chama de "sub-CNFs" ou CNFs com algumas variáveis ​​removidas. mas também o algoritmo DP, davis putnam, pode ser visto como sistematicamente explorando muitos "sub-CNFs" da CNF para resolvê-lo.

[1] Backbones e Backdoors em Satisfability por Kilby et al.