Une solution exacte pour le problème de la couverture du sommet biclique sur un graphique bipartite

Question

Le problème de la couverture du sommet biclique demande si le set de sommet du graphique donné peut être couvert au plus de bicliques "k" (sous-graphes bipartites complets).

Il a été démontré que "Biclique Vertex-Cover" n'est pas un paramètre fixe tractable à moins que p = np dans Couvrir des graphiques avec peu de sous-graphes bipartites complets.

La plupart des travaux dans la littérature ont prouvé la dureté du problème dans les cas généraux / spéciaux. Cependant, J'ai besoin d'un algorithme exact pour résoudre ce problème sur les graphiques bipartites. Un algorithme approximatif avec une garantie est également bon (je suis conscient de "Clustering et problème de partition biclique", mais il a fourni une solution approximative pour" la partition de sommet biclique "et non le sommet du sommet, c'est-à-dire que la solution fournie est pour les bicliques disjoints qui ne se chevauchent pas).

Quelqu'un est-il conscient d'un algorithme exact pour le problème "Biclique Vertex-Cover"? Potentiellement, avec une analyse de complexité temporelle?

Un algorithme naïf, peut-être, à partir de l'ensemble du graphique bipartite pour vérifier un biclique qui couvre tous les sommets (couvrant avec un biclique). Si nous ne réussissons pas, nous vérifions les sous-ensembles en supprimant un sommet et en étudions s'il existe deux bicliques dans cet ensemble qui couvrent tous les sommets (essayant de couvrir avec deux bicliques), et ainsi de suite (essayant de couvrir avec plus de bicliques jusqu'à ce qu'ils atteignent "K")) .