Problema de clique em gráficos fixos

21

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 kkCLIQUE(n,k)GKnnKn1GkKn3kn/2nk

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 GGKnCLIQUE(G,k)S[n]1kSGKnG

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 )nGCLIQUE(G,k)nO(logn)
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(Gn,k)(Gn:n=1,2)

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 aC i | k r = p o l y ( n )C1,,CrGCLIQUE(G,k)rki|SaCi|kr=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 mCLIQUE(m,k)CLIQUE(H,k)Hn=2m[ 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]uv|uv|HGmmkCLIQUE(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 . HmkH m( k - 1 )k(k1)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 v1G=(LR,E)xu+xv1G G C L I Q U E ( G , k )(u,v)EGGCLIQUE(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 BGGO(logn)kGAB|A|+|B|>kAB

Stasys
fonte
mais pensamentos (1) parece que você pode obter um resultado semelhante definindo uma função "filtro" que possui o mesmo número de variáveis ​​que arestas e "filtros" arestas do gráfico fixo com base nos valores 0/1 das variáveis ​​booleanas ... .? isso pode diminuir um pouco a análise devido à construção do gráfico induzido que se move das arestas para os vértices. (2) uma pergunta chave mais simples é incorporada à sua pergunta e, por si só, vale a pena abordar. Quais são alguns gráficos com cliques máximos exponenciais? o exemplo hadamard pode não ser suficiente porque é tão "grande".
fácil
estava estudando algo vagamente semelhante recentemente e se deparou com este factídico interessante: "Uma decomposição de clique gananciosa de um gráfico é obtida removendo cliques máximos de um gráfico, um por um até o gráfico ficar vazio. Recentemente, mostramos que qualquer decomposição de clique gananciosa de um gráfico da ordem tem no máximo 2/4 cliques. " --mcguinnessn 2 / 4nn2/4
vzn
@ vzn: À sua última pergunta. Há uma construção simples (não lembro de quem). Pegue cópias de "anti-trianges" separadas por vértices (triplos de vértices sem arestas entre eles) e coloque as arestas entre todos os vértices de quaisquer dois anti-tringles. O número de cliques máximos é então , e isso é ideal (nada mais é possível). 2 n / 3n/32n/3
Stasys
@vzn: No resultado do McGuinness. Pelo que entendi, ele decompõe todas as arestas em um pequeno número de cliques máximos (tamanho) separados por arestas. Mas pode acontecer que a camarilha máxima do subgráfico induzido não esteja em nenhuma delas. Ainda assim, o resultado parece estar na "direção certa".
Stasys
Sobre a observação 2 : quando você diz que procura uma camarilha em um bipartido, você quer dizer um bipartido completo?
MassimoLauria 04/04

Respostas:

10

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 )GkknΩ(k)

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

MassimoLauria
fonte
11
Um resultado muito bom! Na verdade, minha pergunta surgiu ao tentar mostrar o mesmo resultado para refutações do plano de corte tipo árvore (CP) para o problema (clique). Para derivações em forma de árvore, temos duas (apenas?) Ferramentas: (1) argumentos de complexidade de comunicação e (2) jogos de Pudlak e Impagliazzo com Player-Delayer. A observação 2 implica que (1) falhará (provavelmente) no problema de Clique. Existe alguma analogia de (2) no caso de provas de CP?
Stasys
6

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)

user15669
fonte
2

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.

vzn
fonte
Obrigado pela referência! De fato, esses dois conceitos parecem ser importantes nos solucionadores de SAT. As "backdoors" no nosso caso correspondem a conjuntos de variáveis ​​(= vértices) cuja configuração como 0/1 simplifica o problema de clique. Se houver um pequeno backdoor (logarítmico) , então teremos um pequeno circuito (apenas tentando todas as atribuições para ). Mas admito que os backdoors são grandes para a maioria dos gráficos. SSS
Stasys