Algorithme paramétré pour trouver des bicliques

16

Étant donné un graphe non dirigé à $n$ sommets, quelle est la limite d'exécution la plus connue pour trouver un sous-graphe qui est un $k\times k$ -biclique? Existe-t-il des algorithmes paramétrés plus rapides que l'algorithme de temps consiste à "deviner" un côté de la biclique et à voir s'il y a au moins autres sommets incidents pour chacun d'eux? $\binom{n}{k}\mbox{poly}(n)$ $k$

ds.algorithms reference-request graph-algorithms parameterized-complexity Andreas Björklund
la source

8

Paramétré par la dégénérescence ou l'arboricité, c'est FPT. Plus précisément, où est la dégénérescence (ou pour l'arboricité). Voir: $O(d^3 2^d n)$ $d$ $a^3 2^{2a}$

Arboricité et algorithmes de liste de sous-graphes bipartis. D. Eppstein. Inf. Proc. Lett. 51: 207-211, 1994 .

Un autre article paramétré vient d'être accepté pour SWAT 2012 , cette fois paramétré par la plus longue longueur de chemin induit:

Aistis Atminas, Vadim Lozin et Igor Razgon: algorithme de temps linéaire pour calculer une petite biclique dans des graphiques sans longs trajets induits. SWAT 2012, à paraître.

Mais ma compréhension est que si c'est FPT ou non avec le paramètre naturel (la taille du biclique) est un gros problème ouvert.

David Eppstein
la source

Merci David. Notez que je ne me demande pas seulement si c'est FPT par rapport à k mais plutôt s'il y a quelque chose de mieux que l'algorithme naïf que j'ai esquissé. En particulier, trouve apparemment plus facile que de compter.

Andreas Björklund

5

Les articles suivants fournissent des algorithmes à temps exponentiel pour le problème biclique non induit et peuvent vous intéresser:

Daniel Binkele-Raible, Henning Fernau, Serge Gaspers, Mathieu Liedloff: Algorithmes à temps exponentiel exact pour trouver des bicliques . Inf. Processus. Lett. 111 (2): 64-67 (2010)
Jean-François Couturier, Dieter Kratsch: décors
et bicliques indépendants bicolores . Inf. Processus. Lett. 112 (8-9): 329-334 (2012)

Limath
la source

4

Cette approximation "Minimisation de la norme nucléaire pour les problèmes de clique plantée et de biclique", par B. Ames et S. Vavasis ( http://arxiv.org/pdf/0901.3348.pdf ) trouve une biclique pour certains types spécifiques de graphiques en poly- temps, mais n'a pas de garanties d'approximation générales.

Les auteurs refondent le problème biclique en une minimisation de rang, soumise à des contraintes affines. Ensuite, ils résolvent une relaxation en utilisant une heuristique de norme nucléaire, qui peut être posée comme un SDP. Cette heuristique est un gadget assez excitant de l'attirail de détection compressé. Cette relaxation admet généralement des conditions optimales mignonnes lorsque l'ensemble de contraintes présente "un type approprié" de caractère aléatoire.

Dimitris
la source

-1

$n^{o(k)}$

Elad
la source

6

Je ne pense pas que cette réduction fonctionne. Si votre graphique initial contenait déjà une grosse biclique, le graphique que vous en formez (sa double couverture bipartite) aurait toujours la même biclique, masquant si le graphique d'origine avait également une clique.

David Eppstein

Algorithme paramétré pour trouver des bicliques

Réponses: