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 × k
fonte
Os documentos a seguir fornecem algoritmos de tempo exponencial para o problema de biclique não induzido e podem ser do seu interesse:
Daniel Binkele-Raible, Henning Fernau, Serge Gaspers, Mathieu Liedloff: Algoritmos exatos de tempo exponencial para encontrar bicliques . Inf. Processo. Lett. 111 (2): 64-67 (2010)
Jean-François Couturier, Dieter Kratsch: conjuntos
e bicliques independentes bicolores . Inf. Processo. Lett. 112 (8-9): 329-334 (2012)
fonte
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.
fonte
fonte