Dureza do CLIQUE parametrizado?

17

Seja 0p1 e considere o problema de decisão

CLICK p entrada: número inteiro s , gráfico G com t vértices e arestas Pergunta: O conter uma clique sobre, pelo menos, vértices?p
sGtp(t2)
sGs

Uma instância de CLIQUE p contém uma proporção p de todas as arestas possíveis. Claramente CLIQUE p é fácil para alguns valores de p . CLIQUE 0 0 contém apenas gráficos completamente desconectados e CLIQUE 1 1 contém gráficos completos. Nos dois casos, CLIQUE p pode ser decidido em tempo linear. Por outro lado, para valores de p próximos a 1 1/2 , CLIQUE p é NP-difícil devido a uma redução do próprio CLIQUE: essencialmente, é suficiente para adotar a união disjunta com o gráfico de Turán T(t,s-1 1) .

Minha pergunta:

CLIQUE p está em PTIME ou NP-complete para todos os valores de p ? Ou existem valores de p para os quais CLIQUE p possui complexidade intermediária (se P ≠ NP)?

Essa questão surgiu de uma questão relacionada aos hipergráficos, mas parece interessante por si só.

András Salamon
fonte
11
pergunta interessante !
Suresh Venkat
Pa é um número real entre 0 e 1 ou p pode ser uma função de t?
Robin Kothari
@ Robin: Eu não especifiquei, ambos seriam interessantes.
András Salamon
3
Se a proporção de arestas for um limite superior (e não um requisito exato de contagem ou um limite inferior), para qualquer constante 0<p<1 esse problema será NP-rígido por redução do CLIQUE: Adicione um conjunto suficientemente grande de vértices isolados . O requisito de que as arestas numéricas sejam iguais à expressão especificada? Ou que coisa claramente óbvia estou perdendo? :-)
gphilip 19/09/10
11
@ gphilip: Como você aponta, a redução é imediata se a proporção for apenas um limite superior; é por isso que a pergunta é formulada em termos da proporção exata.
András Salamon

Respostas:

14

Suponho que o número na definição do problema CLIQUE p seja exatamente igual ao número de arestas no gráfico, diferentemente do comentário do gphilip à pergunta.p(t2)

O problema CLIQUE p é NP-completo para qualquer constante racional 0 < p <1 por uma redução do problema CLIQUE usual. (A suposição de que p é racional é necessária apenas para que possa ser calculado a partir de N no polinômio de tempo em N ).pN

Seja k ≥3 um número inteiro que satisfaça k 2 ≥1 / pe (1−1 / k ) (1−2 / k )> p . Dado um gráfico G com n vértices e m arestas juntamente com um valor limite s , a redução funciona da seguinte maneira.

  1. Se s < k , resolvemos o problema da CLIQUE no tempo O ( n s ). Se houver um clique de tamanho pelo menos s , produzimos uma instância sim fixa. Caso contrário, produzimos uma não instância fixa.
  2. Se n < s , produzimos uma não instância fixa.
  3. Se nsk , adicionamos ao gráfico de partições G a ( k −1) onde cada conjunto consiste em n vértices que possuem exatamente arestas e produza este gráfico.p(nk2)-m

Observe que o caso 1 leva tempo O ( n k −1 ), que é polinomial em n para cada p . O caso 3 é possível porque se nsk , então é não-negativo e, no máximo, o número de arestas no total ( k −1) -partite gráfico K n ,…, n como mostrado nas duas reivindicações a seguir.p(nk2)-m

Reivindicação 1 . .p(nk2)-m0 0

Prova . Como , basta provarmos ou equivalentemente pnk ( nk −1) ≥ n ( n -1). Como p ≥ 1 / k 2 , temos pnk ( nk −1) ≥ n ( n −1 / k ) ≥ n ( n −1). QED . p ( nkm(n2)p(nk2)(n2)

Reivindicação 2 . . (Observe que o lado direito é o número de arestas no gráfico completo (K − 1) de partes de K n ,…, n .)p(nk2)-m<n2(k-1 12)

Prova . Como e m ≥ 0, basta provarmos ou equivalentemente n 2 ( k −1) ( k −2) - pnk ( nk −1) - 2 ≥ 0. Como p <(1−1 / k ) (1−2 / k ), temos QED .p ( n kx<x+1 1 n2(k-1)(k-2)-pnk(nk-1)-2n2(k-1)(k-2)-n(n-p(nk2)+1 1n2(k-1 12)

n2(k-1 1)(k-2)-pnk(nk-1 1)-2
n2(k-1 1)(k-2)-n(n-1 1k)(k-1 1)(k-2)-2
=nk(k-1 1)(k-2)-2(k-1 1)(k-2)-20

Editar : a redução na revisão 1 teve um erro; às vezes exigia um gráfico com número negativo de arestas (quando p era pequeno). Este erro foi corrigido agora.

Tsuyoshi Ito
fonte
isso é o mais próximo do fraseado específico, então obrigado por abordá-lo. O caso 3 é o mais próximo do que eu tinha em mente. No entanto, não sigo o cálculo - você poderia expandir um pouco?
András Salamon
@ András Salamon: Feito.
Tsuyoshi Ito
15

Se pode ser uma função de t , então o problema pode ser intermediário. Configure p para que o número de arestas seja log 4 t . Então, obviamente, s pode ter no máximo log 2 te, portanto, existe um algoritmo t log 2 t para esse problema, o que significa que o problema (sob suposições padrão, digamos que SAT não possui algoritmos subexponenciais) não pode ser difícil para NP.ptpregistro4tsregistro2ttregistro2t

registro2t

p

Boaz Barak
fonte