2025-11-21T03:46:15.611457

A Faster Randomized Algorithm for Vertex Cover: An Automated Approach

Clinch, Gaspers, He et al.

This work introduces two techniques for the design and analysis of branching algorithms, illustrated through the case study of the Vertex Cover problem. First, we present a method for automatically generating branching rules through a systematic case analysis of local structures. Second, we develop a new technique for analyzing randomized branching algorithms using the Measure & Conquer method, offering greater flexibility in formulating branching rules. By combining these innovations with additional techniques, we obtain the fastest known randomized algorithms in different parameters for the Vertex Cover problem on graphs with bounded degree (up to 6) and on general graphs. For example, our algorithm solves Vertex Cover on subcubic graphs in $O^*(1.07625^n)$ time and $O^*(1.13132^k)$ time, respectively. For graphs with maximum degree 4, we achieve running times of $O^*(1.13735^n)$ and $O^*(1.21103^k)$, while for general graphs we achieve $O^*(1.25281^k)$.

academic

Un Algorithme Randomisé Plus Rapide pour la Couverture de Sommets : Une Approche Automatisée

Informations Fondamentales

ID de l'article : 2510.09027
Titre : A Faster Randomized Algorithm for Vertex Cover: An Automated Approach
Auteurs : Katie Clinch (University of Queensland), Serge Gaspers (UNSW Sydney), Tao Zixu He (University of Massachusetts Amherst), Simon Mackenzie (UNSW Sydney), Tiankuang Zhang (UNSW Sydney)
Classification : cs.DS (Structures de Données et Algorithmes), cs.CC (Complexité Computationnelle)
Date de Publication : 2025
Lien de l'article : https://arxiv.org/abs/2510.09027

Résumé

Cet article introduit deux nouvelles techniques pour la conception et l'analyse d'algorithmes de branchement appliqués au problème de la couverture de sommets. Premièrement, une méthode de génération automatique de règles de branchement par analyse systématique de cas de structures locales est proposée. Deuxièmement, une nouvelle technique d'analyse d'algorithmes de branchement randomisés utilisant la méthode Measure & Conquer est développée, offrant une plus grande flexibilité dans la formulation des règles de branchement. En combinant ces innovations avec d'autres techniques, les algorithmes randomisés les plus rapides connus pour le problème de la couverture de sommets sur les graphes de degré borné (degré maximal jusqu'à 6) et les graphes généraux sont obtenus. Par exemple, l'algorithme atteint un temps d'exécution de $O^*(1.07625^n)$ et $O^*(1.13132^k)$ sur les graphes cubiques, $O^*(1.13735^n)$ et $O^*(1.21103^k)$ sur les graphes de degré maximal 4, et $O^*(1.25281^k)$ sur les graphes généraux.

Contexte et Motivation de la Recherche

Importance du Problème

Le problème de la couverture de sommets est l'un des problèmes NP-complets les plus classiques en informatique, étudié depuis plus de 50 ans. Étant donné un graphe $G = (V, E)$ et un entier $k$ , il s'agit de déterminer s'il existe un sous-ensemble de sommets $C \subseteq V$ de taille au plus $k$ couvrant toutes les arêtes. Ce problème revêt une importance capitale tant en informatique théorique que dans les applications pratiques.

Limitations des Approches Existantes

Limitations de la conception manuelle : Bien que les algorithmes de branchement exacts soient parmi les outils les plus efficaces pour résoudre les problèmes NP-difficiles, ils reposent principalement sur une conception manuelle, nécessitant une analyse de cas personnalisée et des mesures soigneusement ajustées pour chaque nouveau problème.
Faible portabilité : Ce processus manuel limite la portabilité des algorithmes et ralentit la progression de la recherche.
Analyse de randomisation insuffisante : Les méthodes Measure & Conquer existantes sont principalement destinées aux algorithmes déterministes, manquant d'une approche systématique pour analyser les algorithmes de branchement randomisés.

Motivation de la Recherche

Cet article soutient que la majorité du travail de conception d'algorithmes de branchement peut être automatisée, proposant un cadre pour :

Explorer systématiquement les configurations locales
Simplifier la recherche par fusion de classes d'équivalence
Générer des règles de branchement déterministes ou randomisées de haute qualité en résolvant des formulations LP/ILP optimisant directement la progression des mesures

Contributions Principales

Measure & Conquer Randomisé : Extension de Measure & Conquer à l'analyse du temps d'exécution des algorithmes randomisés, permettant à M&C de traiter efficacement les règles de branchement probabilistes.
Génération Automatique de Règles basée sur LP/ILP : Introduction d'un cadre novateur qui formule la sélection de règles et l'attribution de poids comme un problème d'optimisation maximisant directement la réduction de mesure, supportant naturellement les règles déterministes et randomisées.
Temps d'Exécution Améliorés pour la Couverture de Sommets : Les algorithmes générés améliorent les meilleures bornes paramétrées connues pour les graphes généraux et diverses situations de degré borné, notamment :
- Graphes cubiques : $O^*(1.07625^n)$ et $O^*(1.13132^k)$
- Graphes de degré 4 : $O^*(1.13735^n)$ et $O^*(1.21103^k)$
- Graphes généraux : $O^*(1.25281^k)$

Détails Méthodologiques

Définition du Problème

Problème de Couverture de Sommets : Étant donné un graphe non orienté $G = (V, E)$ et un entier non négatif $k$ , déterminer s'il existe un sous-ensemble de sommets $C \subseteq V$ tel que $|C| \leq k$ et $C$ couvre toutes les arêtes (c'est-à-dire que chaque arête a au moins une extrémité dans $C$ ).

Cadre Technique Principal

1. Measure & Conquer Randomisé

Lemme 2 : Soit $A_r$ un algorithme de branchement randomisé pour le problème de décision $\Pi$ , et $\mu(\cdot)$ une mesure non négative des instances de $\Pi$ . Pour toute instance $I$ , $A_r$ résout soit $I$ en temps constant lorsque $\mu(I) = 0$ , soit réduit $I$ à des sous-instances $I_1, \ldots, I_k$ avec poids correspondants $w_1, \ldots, w_k$ .

Contrainte clé : $\sum_{i=1}^k w_i \cdot 2^{\mu(I_i)} \leq 2^{\mu(I)}$

La sous-instance $I_i$ est sélectionnée aléatoirement avec probabilité au moins $w_i \cdot 2^{\mu(I_i)-\mu(I)}$ .

2. Configurations Locales et Couverture Étendue

Définition 3 (Configuration Locale) : Une configuration locale pour le problème de couverture de sommets est définie comme le tuple $L = (H, D)$ , où $H = (V, E)$ est un graphe et $D$ est une fonction mappant chaque sommet au nombre d'arêtes incidentes incomplètes.

Algorithme 2 (Algorithme d'Extension) :

Sélectionner un sommet frontière $v$ avec degré minimal et le moins d'arêtes incomplètes
Pour chaque $u_i \in \delta(L) \setminus \{v\}$ , créer une nouvelle configuration locale connectant $v-u_i$
Pour chaque $i \in \{1, \ldots, \Delta\}$ , ajouter un nouveau sommet $u$ de degré $i$ et le connecter à $v$

3. Conception de la Mesure

Utilisation de la mesure : $\mu = \alpha k + \beta_1 n_1 + \beta_2 n_2 + \beta_3 n_3$

où $k$ est la taille de la couverture de sommets, $n_i$ représente le nombre de sommets de degré $i$ , et $\alpha, \beta_1, \beta_2, \beta_3$ sont des poids.

Contraintes :

Pour les algorithmes paramétrés par $n$ : $\alpha = 0$ et $\beta_3 \geq 0$ , donnant $0 \leq \frac{3\beta_1}{4} \leq \frac{3\beta_2}{4} \leq \beta_3$
Pour les algorithmes paramétrés par $k$ : $\beta_i \leq 0$ ( $i \in \{1,2\}$ ) et $\beta_3 = 0$

4. Génération de Règles de Branchement

Formulation de Programmation Linéaire : $\min_w \sum_{b_i \in B} w_i \cdot \text{coût}(L, b_i)$ $\text{s.c. } \forall R_i \in \mathcal{R} \sum_{b_j \in B: R_i \in EB(L,b_j,\mathcal{R})} w_j \geq 1$ $\forall b_i \in B: w_i \in [0,1]$

Points d'Innovation Technique

Extension Centrée sur les Arêtes : Contrairement à l'expansion précédente sommet par sommet, l'adoption d'une expansion arête par arête réduit significativement le nombre de configurations candidates.
Contrôle de la Redondance : Élimination des doublons par partitionnement de l'espace d'instances et fusion des configurations locales isomorphes, évitant les coûts de requêtes fréquentes d'isomorphisme de sous-graphes.
Cadre d'Optimisation Unifié : Formulation de la sélection de règles et de l'attribution de poids comme un problème d'optimisation LP/ILP unique, maximisant directement la progression de mesure et supportant sans interruption le branchement randomisé.

Configuration Expérimentale

Environnement de Test

Utilisation de deux mesures : $\mu_1 = 0.106n_3$ (paramètre $n$ ) et $\mu_2 = 0.178k - 0.0445n_1 - 0.089n_2$ (paramètre $k$ )
Partition de l'espace d'instances des graphes cubiques en 19 sous-espaces pour optimisation
Détection d'isomorphisme de graphes utilisant la bibliothèque Nauty, résolution LP utilisant ALGLIB

Règles de Simplification

Implémentation de 5 règles de simplification :

Règle des sommets isolés
Règle des sommets de degré 1
Règle des triangles de degré 2
Règle des chaînes de degré 2
Règle des cycles alternés

Références de Comparaison

Comparaison avec les résultats les plus récents :

Graphes cubiques : $O^*(1.08351^n)$ et $O^*(1.14416^k)$ de Xiao & Nagamochi
Graphes de degré 4 : $O^*(1.13760^n)$ et $O^*(1.21131^k)$ de Xiao & Nagamochi
Graphes généraux : $O^*(1.25284^k)$ de Harris & Narayanaswamy

Résultats Expérimentaux

Résultats Principaux

Degré Maximal	Paramètre	Nouvelle Borne	Borne Précédente
∆ ≤ 3	n	$O^*(1.07625^n)$	$O^*(1.08351^n)$
	k	$O^*(1.13132^k)$	$O^*(1.14416^k)$
∆ ≤ 4	n	$O^*(1.13735^n)$	$O^*(1.13760^n)$
	k	$O^*(1.21103^k)$	$O^*(1.21131^k)$
∆ ≤ 5	k	$O^*(1.24382^k)$	$O^*(1.24394^k)$
∆ ≤ 6	k	$O^*(1.25210^k)$	$O^*(1.25214^k)$
Graphes Généraux	k	$O^*(1.25281^k)$	$O^*(1.25284^k)$

Réalisations Techniques

Améliorations Significatives pour les Graphes Cubiques : Améliorations substantielles obtenues sur les paramètres $n$ et $k$
Améliorations pour les Graphes de Degré 4 : Améliorations obtenues en utilisant l'algorithme amélioré pour graphes cubiques comme sous-programme
Améliorations pour les Graphes Généraux : Améliorations obtenues par intégration dans le cadre Harris-Narayanaswamy

Validation de la Méthode

Validation des améliorations via le Lemme 19 : $d = \frac{2c(a+b)}{a+2c}$ où $c$ est l'exposant de l'algorithme exact, $a,b$ sont les coefficients de mesure de l'algorithme FPT.

Travaux Connexes

Génération Automatique d'Algorithmes

Gramm et al. : Pionniers de la génération automatique pour Cluster Editing
Fedin & Kulikov : Générateur proposé pour les problèmes SAT
Červený & Suchý : Adaptation du paradigme à d-Path Vertex Cover

Algorithmes Randomisés Exacts

Monotone Local Search : Amélioration du temps d'exécution pour des dizaines de problèmes NP-complets
Algorithmes Probabilistes : Tels que l'algorithme k-SAT de Schöning

Méthode Measure & Conquer

La M&C traditionnelle est principalement destinée aux algorithmes déterministes ; cet article étend systématiquement pour la première fois cette méthode à l'analyse d'algorithmes randomisés.

Conclusion et Discussion

Conclusions Principales

Transformation réussie de la conception manuelle de branchement en pipeline de recherche optimisée
Du côté de l'analyse, extension de Measure & Conquer au branchement randomisé, fournissant une approche systématique pour les bornes supérieures du temps d'exécution avec sélection probabiliste
Du côté de la génération de règles, formulation de la découverte de branchement et de l'attribution de poids comme objectif LP/ILP optimisant directement la progression de mesure

Limitations

Sélection de Mesure : L'implémentation actuelle suppose que l'utilisateur spécifie la mesure et les poids correspondants, vérifiant uniquement leur faisabilité
Restriction de Degré : La résolution directe du problème de couverture de sommets pour les graphes de haut degré nécessite de traiter plus de configurations
Ajustement Automatique des Poids : À mesure que la mesure devient plus complexe, l'identification des poids appropriés devient progressivement plus difficile

Directions Futures

Ajustement Automatique des Poids : Ajustement automatique des poids lors de l'extension de configurations
Traitement des Graphes de Haut Degré : Développement de stratégies intelligentes pour les graphes de degré plus élevé
Application Plus Large : Application du cadre à une gamme plus large de problèmes de sous-ensemble

Évaluation Approfondie

Avantages

Innovation Théorique : Measure & Conquer randomisé comble une lacune théorique importante
Systématicité de la Méthode : Fourniture d'un cadre complet d'automatisation, de la génération de configurations à l'optimisation de règles
Valeur Pratique : Réalisation des meilleurs résultats connus sur plusieurs instances de problèmes importants
Extensibilité : Conception modulaire du cadre, applicable indépendamment à d'autres problèmes

Insuffisances

Complexité : Implémentation du cadre relativement complexe, nécessitant une expertise spécialisée pour l'ajustement
Portée d'Application : Principalement applicable aux problèmes possédant une structure locale
Coût Computationnel : La résolution LP/ILP peut devenir un goulot d'étranglement

Impact

Contribution Théorique : Fourniture de nouveaux outils pour l'analyse d'algorithmes de branchement randomisés
Valeur Pratique : Réduction significative de l'effort manuel dans la conception d'algorithmes de branchement
Reproductibilité : Fourniture d'une implémentation open-source facilitant la vérification et l'extension

Scénarios d'Application

Problèmes de Sous-ensemble : Problèmes de sous-ensemble avec interactions locales bornées
Problèmes de Graphes : Particulièrement les problèmes de graphes avec contraintes de degré
Algorithmes Paramétrés : Problèmes paramétrés nécessitant des algorithmes exacts exponentiels

Références

L'article cite 24 références importantes couvrant les algorithmes paramétrés, les algorithmes exacts, la génération automatique d'algorithmes et d'autres domaines connexes, fournissant une base théorique solide pour la recherche.

Évaluation Globale : Cet article constitue une contribution importante de haute qualité au domaine de l'informatique théorique, présentant des percées tant sur le plan technique que dans les applications pratiques. La proposition de la méthode Measure & Conquer randomisé comble une lacune théorique, et la conception du cadre d'automatisation offre des perspectives d'application largement applicables.