Trouver des bicliques dans un graphique bipartite de taille minimale

Question

Soit $ g = (u cup v, e) $ désigne un graphique bipartite. Un biclique $ c = (u, v) $ est un sous-graphique de $ g $ induit par une paire de deux sous-ensembles disjoints $ u ' subseseq u $, $ v' subseseq v $, tel que $ forall u in U ', v in v': (u, v) in e $.

Étant donné $ delta $, je voudrais identifier les bicliques $ (u ', v') $ tels que $ | v '| ge delta $. Étant donné que le nombre de tous les bicliques dans un graphique bipartite Wrt sa taille peut être exponentiel, je recherche un algorithme approximatif (souhaitablement avec des garanties), qui peuvent trouver des bicliques tels que $ | v '| ge delta $. Par exemple, trouver $ k $ bicliques où $ | v '| geq delta $, dans le temps polynomial wrt $ k $ et $ g $. Quelqu'un peut-il suggérer un tel algorithme?

Une solution naïve consiste à énumérer les bicliques en utilisant un algorithme basé sur l'énumération et à garder les bicliques qui satisfont la dernière condition jusqu'à la sélection des bicliques "k".