Comment générer des graphiques avec une couverture de sommet optimale connue

Je cherche un moyen de générer des graphiques pour que la couverture optimale des sommets soit connue. Il n'y a aucune restriction sur le nombre de nœuds ou d'arêtes, seulement que le graphique est complètement connecté.

l'idée est de générer un graphe qui n'est pas facile de trouver la couverture de sommet optimale, pour pouvoir tester différentes heuristiques dessus

J'ai trouvé l'article Arthur, J. & Frendeway, J. Generating Travelling-Salesman Problems with Known Optimal Tours, The Journal of the Operational Research Society, Vol. 39, n ° 2 (février 1988), pp. 153-159 pour générer un TSP avec l'optimum connu, hélas je ne peux pas y accéder.

Existe-t-il un algorithme connu?

ds.algorithms graph-theory graph-algorithms AndresQ
la source

"Il n'y a aucune restriction sur le nombre de nœuds ou d'arêtes, seulement que le graphique est complètement connecté." Vous avez besoin de plus de restrictions que cela. Sinon, je génère l'ensemble des graphes complets et connais les couvertures de vertex optimales pour chacun.

Tyson Williams

Voici une approche très simple: Tout d'abord, construisez un correspondant . Pour chaque arête , ajoutez un point final à votre couverture de sommet . Ajoutez ensuite un nombre quelconque de nœuds supplémentaires. Puis ajouter un nombre quelconque d'arêtes, de sorte que chaque bord présente au moins un point d' extrémité en . Nécessairement, sera une couverture minimale des sommets. (Malheureusement, il existe de nombreux graphiques qui ne peuvent pas être générés de cette façon: par exemple, .)

M

$M$

e \in M

$e \in M$

C

$C$

C

$C$

C

$C$

K_{3}

$K_3$

Jukka Suomela

Je suppose que "générer un graphe bipartite aléatoire et calculer sa couverture de sommet" ne compte pas comme une réponse utile ...

David Eppstein

il existe de nombreuses stratégies pour créer des instances SAT "dures" et également des référentiels d'instances "dures" archivées si vous êtes prêt à emprunter cette voie, c'est-à-dire convertir une instance de SAT en couverture de vertex. il y a aussi beaucoup de recherches étudiant SAT à partir d'un point de vue empirique qui se traduit naturellement par tous les autres problèmes NP complets, par exemple le point de transition, etc. de nombreuses références sur tout cela ...

vzn

Encore plus généralement que la solvabilité polynomiale temporelle de la couverture Vertex sur les graphes de Koning comme l'a noté David, le résultat suivant est connu dans le domaine de la complexité paramétrée: il y a une constante c telle que pour chaque entier fixe k, il y a un O (n ^ c) algorithme de temps pour tester si un graphe a une couverture de sommet qui dépasse sa taille de correspondance maximale d'au plus k. Les graphes de Konig sont le cas particulier lorsque k = 0.

Bart Jansen

Réponses:

Élargir le commentaire de vzn en réponse: La réduction standard de CNF-SAT à la couverture des sommets est assez facile: créer un sommet pour chaque terme (variable ou sa négation), connecter chaque variable à sa négation par un bord, faire une clique pour chaque clause et connectez chaque sommet de la clique au sommet pour l'un des termes de la clause. Si vous commencez avec un problème de satisfiabilité avec une affectation satisfaisante connue, cela vous donnera un problème de couverture de sommet avec une solution optimale connue (choisissez le terme sommets donné par l'affectation, et dans chaque clause, choisissez tous les sommets sauf un, de sorte que le le sommet de la clause qui n'est pas choisi est adjacent à un sommet qui est choisi).

Alors maintenant, vous devez trouver des problèmes de satisfiabilité qui ont une affectation satisfaisante connue mais où la solution est difficile à trouver. Il existe de nombreuses manières connues de générer des problèmes de satisfiabilité difficiles (par exemple, générer des instances k-SAT aléatoires proches du seuil de satisfiabilité) mais l'exigence supplémentaire que vous connaissiez l'affectation satisfaisante limite les possibilités. Une chose que vous pouvez faire ici est de passer par un autre niveau de réduction, à partir d'un problème cryptographiquement difficile tel que la factorisation. C'est-à-dire choisir deux grands nombres premiers p et q, mettre en place un circuit booléen pour multiplier p et q en nombres binaires, et le traduire en une formule CNF dans laquelle il y a une variable pour chaque entrée (p et q) et pour chaque valeur intermédiaire sur un fil dans le circuit, une clause pour chaque sortie l'obligeant à avoir la bonne valeur, et une clause pour chaque porte forçant les entrées et sorties de la porte à être cohérentes entre elles. Traduisez ensuite cette formule CNF en couverture de vertex.

Pour une stratégie plus simple, choisissez d'abord l'affectation satisfaisante à une formule 3CNF, puis générez des clauses au hasard, en ne conservant que les clauses qui sont cohérentes avec l'affectation, puis convertissez-les en couverture de vertex. Si les clauses ont une probabilité uniforme, cela sera vulnérable à une heuristique basée sur les degrés (le terme sommets qui correspondent à l'affectation choisie aura un degré inférieur à celui des sommets qui ne le sont pas) mais cette lacune peut être évitée en ajustant les probabilités des clauses selon le nombre de termes de la clause en accord avec l'affectation choisie. Cela est probablement vulnérable à une sorte d'attaque temporelle polynomiale, mais ce n'est peut-être pas une attaque naturelle pour la couverture des sommets, donc cela pourrait constituer un bon ensemble d'instances de test malgré une faible garantie de dureté.

David Eppstein
la source

\cap

$\cap$

la référence la plus proche que j'ai trouvée était-- Sur des exemples difficiles de couverture approximative de sommets par Sundar Vishwanathan. n'a pas vu de références pour regarder des instances dures du problème exact.

comme dans mon commentaire, il y a beaucoup de recherches sur cette approche correspondante pour SAT qui est réductible à la couverture des vertex.

Concernant le commentaire des DE, l'idée de générer des instances aléatoires et de simplement choisir les instances difficiles pour un algorithme standard me semble tout à fait raisonnable, en particulier avec une approche de recherche empirique / expérimentale [1], c'est un mode opératoire standard pour des recherches similaires sur le SAT point de transition. [2]

qui a d'ailleurs quelque chose à dire où se trouve la région "dure" pour tout autre problème NP complet [3,4,5] qui se rapporte à peu près à un point critique de la "densité" de 1 dans des cas aléatoires spécifiés en binaire. pour la couverture des sommets, cela correspondrait probablement à la densité des bords.

notez que prouver que l'on peut construire un ensemble d'instances dures, et uniquement des instances dures, est fondamentalement équivalent au problème P vs NP. une analyse plus formelle de cette équivalence se trouve dans l'article Razborov / Rudich Natural Proofs.

[1] algorithmique expérimentale

[2] Recherche sur la transition de phase SAT

[3] Transitions de phase dans les problèmes difficiles NP

[4] Transitions de phase dans les problèmes NP-complets: un défi pour la probabilité, la combinatoire et l'informatique par Moore

[5] Comportement de transition de phase par Walsh

vzn
la source