Una soluzione esatta per il problema della copertura del vertice Biclique su un grafico bipartito

Question

Il problema della copertura del vertice biclique chiede se il set di vertice del grafico dato può essere coperto con il massimo da "K" bicliques (sottogruppi bipartiti completi).

È stato dimostrato che la "copertura del vertice biclique" non è un trattabile a parametro fisso a meno che p = np in Copertura di grafici con pochi sottografici bipartiti completi.

La maggior parte del lavoro in letteratura ha dimostrato la durezza del problema in casi generali/speciali. Tuttavia, Ho bisogno di un algoritmo esatto per risolvere questo problema sui grafici bipartiti. Un algoritmo approssimativo con una garanzia è anche buono (sono a conoscenza "Clustering e il problema della partizione Biclique", Ma ha fornito una soluzione approssimativa per" Biclique Vertex Partition "non copertura vertice, cioè la soluzione fornita è per i bicliques disgiunti non eventualmente sovrapposti).

Qualcuno è a conoscenza di un algoritmo esatto per il problema "Biclique Vertex-Cover"? Potenzialmente, con l'analisi della complessità del tempo?

Un algoritmo ingenuo, forse, inizierebbe dall'intero grafico bipartito per verificare una biclique che copre tutti i vertici (che coprono con una biclique). Se non è riuscito, controlliamo i sottoinsiemi rimuovendo un vertice e indaghiamo se esistono due biclique in questo set che coprono tutti i vertici (cercando di coprire due bicliques) e così via (cercando di coprire più biclique fino a raggiungere "k") .