Trovare bicliques in un grafico bipartito di dimensioni minime

Question

Lascia che $ g = (u coppa V, e) indica un grafico bipartito. A Biclique $ c = (u, v) $ è un sottografo di $ g $ indotto da una coppia di due sottoinsiemi disgiunti $ u ' sottoseteq u $, $ v' sottoseteq v $, tale che $ forall u in U ', v in v': (u, v) in e $.

Dato $ Delta $, vorrei identificare bicliques $ (u ', v') $ tale che $ | v '| ge Delta $. Poiché il numero di tutti i biclique in un grafico bipartito, le sue dimensioni possono essere esponenziali, sto cercando Un algoritmo approssimativo (desiderabilmente con garanzie), che può trovare bicliques tale che $ | V '| ge Delta $. Per esempio, Trova $ K $ Bicliques dove $ | V '| geq Delta $, col tempo polinomiale wrt $ k $ e $ g $. Qualcuno può suggerire un tale algoritmo?

Una soluzione ingenua è quella di enumerare i bicliques usando un algoritmo basato sull'enumerazione e mantenere i bicliques che soddisfano l'ultima condizione fino alla selezione di bicliques "K".