Algoritmo Parametrizado para Encontrar Bicliques

16

Dado um gráfico não direcionado de vértices , qual é o tempo de execução mais conhecido para encontrar um subgráfico que é uma biclique ? Existem algoritmos parametrizados mais rápidos que o algoritmo de tempo \ binom {n} {k} \ mbox {poly} (n) de "adivinhar" um lado da biclique e ver se há pelo menos k outros vértices incidentes em todos eles?k × knk×k(nk)poly(n)k

Andreas Björklund
fonte

Respostas:

8

Parametrizado por degenerescência ou arboricidade, é o FPT. Mais especificamente, O(d32dn) onde d é a degenerescência (ou a322a para arboricidade). Vejo:

Outro artigo parametrizado acaba de ser aceito no SWAT 2012 , desta vez parametrizado pelo maior comprimento do caminho induzido:

  • Aistis Atminas, Vadim Lozin e Igor Razgon: algoritmo de tempo linear para calcular uma pequena biclique em gráficos sem longos caminhos induzidos. SWAT 2012, para aparecer.

Mas meu entendimento é que se esse é o FPT ou não com o parâmetro natural (o tamanho do biclique) é um grande problema em aberto.

David Eppstein
fonte
Obrigado David. Note que não estou apenas me perguntando se é FPT wrt k, mas se há algo melhor que o algoritmo ingênuo que eu esbocei. Em particular, é aparentemente mais fácil do que contar.
Andreas Björklund 31/03
5

Os documentos a seguir fornecem algoritmos de tempo exponencial para o problema de biclique não induzido e podem ser do seu interesse:

Limath
fonte
4

Essa aproximação "Minimização da norma nuclear para os problemas de camarilha e biclique plantada", de B. Ames e S. Vavasis ( http://arxiv.org/pdf/0901.3348.pdf ), encontra uma biclique para algum tipo específico de gráfico em poli- tempo, mas não tem garantias gerais de aproximação.

Os autores reformulam o problema da biclique para uma minimização de classificação, sujeita a restrições afins. Em seguida, eles resolvem um relaxamento usando uma heurística de norma nuclear, que pode ser colocada como um SDP. Essa heurística é um gadget bastante interessante da parafernália de sensores compactados. Esse relaxamento geralmente admite algumas condições fofas de otimalidade quando o conjunto de restrições exibe "um tipo apropriado" de aleatoriedade.

Dimitris
fonte
-1

no(k)

Elad
fonte
6
Eu não acho que essa redução funcione. Se o seu gráfico inicial já continha uma grande biclique, o gráfico que você formar (sua capa dupla bipartida) ainda teria a mesma biclique, mascarando se o gráfico original também tinha uma clique.
David David Eppstein