Nombre de sommets présents dans toutes les correspondances maximales

Étant donné un graphe , nous devons trouver la cardinalité du plus grand ensemble de sommets afin que chacun d'eux soit présent dans chaque correspondance maximale possible. $G$

Existe-t-il une solution à côté de l'évidence, supprimez chaque sommet et trouvez la correspondance maximale pour la voir réduire?

graph-theory graph-algorithms Hououin Kyouma
la source

Je ne vois pas en quoi ce que vous proposez est même une solution.

$\:$ (Considérez un triangle.)

$\hspace{1.4 in}$

@RickyDemer nous trouvons d'abord la correspondance maximale dans tout le graphique. Ensuite, nous supprimons un sommet et retrouvons la correspondance maximale. Si la différence est 1, alors nous pouvons dire que ce sommet est présent dans toutes les correspondances maximales.

evil999man

Faut-il remplacer «trouver une correspondance maximale» par «trouver une correspondance maximale» ou «trouver toutes les correspondances maximales»?

$\;$

Je pense qu'il devrait être remplacé par une taille de correspondance maximale.

evil999man

@Awesome a raison. Je vais modifier ma question.

Hououin Kyouma

Réponses:

$O(n^3)$

Thomas Kalinowski
la source

Je n'ai besoin que de taille, pas des sommets eux-mêmes. Cela peut-il être fait en O (n ^ 2)? Et merci pour le papier

Hououin Kyouma

$v$

En effectuant deux recherches en largeur ou en profondeur d'abord, une pour trouver les parties du graphique qui peuvent être atteintes à partir de sommets sans correspondance et l'autre pour trouver les parties qui peuvent atteindre des sommets sans correspondance, vous pouvez trouver les sommets essentiels en temps linéaire une fois que vous ont déjà la correspondance.

Probablement quelque chose comme cela fonctionnera également pour le cas non bipartite, en utilisant une recherche de chemin alternatif contractant les fleurs, mais les détails seront plus compliqués.

David Eppstein
la source

Je suis curieux de savoir comment vous le feriez dans un graphique général. Pourriez-vous l'expliquer?

evil999man

Si je l'avais déjà élaboré en détail, je l'aurais inclus dans ma réponse. Mais fondamentalement, vous voulez simplement trouver les sommets qui peuvent être atteints en alternant les chemins à partir des sommets non atteints, car ce sont ceux qui pourraient éventuellement rester sans correspondance. La recherche de chemin alterné devrait être à peu près la même que celle que vous utilisez pour trouver la correspondance en premier lieu.

David Eppstein

Désolé pour un commentaire tardif. Mon graphique est général. Je vais essayer de réfléchir à la méthode

Hououin Kyouma