Complexite Parametree -- k-Vertex Cover

Etude experimentale approfondie des algorithmes de kernelization pour le probleme k-Vertex Cover. Implementation de la decomposition en couronne et des regles de reduction pour obtenir un noyau polynomial de taille 3k. Architecture modulaire en Python avec NetworkX incluant generateurs de graphes, algorithmes de matching bipartite et evaluateur branch-and-reduce.

Analyse comparative rigoureuse entre l'approche VCB directe et l'approche hybride (kernelization + VCB sur le noyau reduit). Speedup jusqu'a 5000x sur graphes denses, reduction de 40-50% des sommets pour faibles ratios k/n. Evaluation sur instances aleatoires G(n,p) et graphes avec vertex cover garanti.