Recoloration des graphes bipartis

Étant donné un graphique bipartite $G = (A,B,E)$ où chaque sommet est coloré en rouge ou en bleu, j'essaie de minimiser le nombre de sommets bleus en utilisant l'opération suivante:

1. Choisissez un sommet $v_a$ dans $A$
2. Retournez les couleurs de $N[v_a]$, ce qui signifie que $v_a$ et chaque voisin de $v_a$ changera de couleur.

Existe-t-il un algorithme de temps polynomial pour sélectionner un ensemble de recoloration $X \subseteq A$qui minimisera le nombre de sommets bleus? Le nombre de recolorations nécessaires n'est pas pertinent.

Observez que l'ordre de retournement n'a pas d'importance, et pour chaque sommet de $A$, soit vous le retournez, soit vous ne le faites pas. Nous pouvons penser aux couleurs comme un nombre qui est incrémenté modulo 2. Cela donne un trivial$O(2^{|A|} \cdot n)$ algorithme.

Le problème est NP-complet et n'est donc pas susceptible d'admettre un algorithme de temps polynomial. Vous trouverez ci-dessous une preuve de la complétude NP du problème, illustrée par une réduction de 1-en-3-SAT.

Laisser $\phi$être une instance de 1-IN-3-SAT, où l'on nous donne une formule 3-CNF-SAT demandée pour trouver une affectation satisfaisante où chaque clause est satisfaite par exactement un littéral. Laisser$V(\phi)$ être l'ensemble des $n$ les variables, et $C(\phi)$ être l'ensemble des $m$ clauses.

Nous construisons une instance $G = (A,B,E)$ avec un budget de $b = n + m$ (le nombre autorisé de sommets bleus).

Pour chaque variable $x \in V(\phi)$, construire deux sommets rouges $v_x$ et $v_{\overline{x}}$ dans $A$ ensemble avec $b+1$ sommets bleus dans $B$à côté de chacun d'eux. Cela force exactement l'un des$v_x$ ou $v_{\overline{x}}$à retourner. On se retrouve aussi avec$n$ inversé les "sommets variables", utilisant ainsi la première partie du budget.

Remarque: $\{v_x, v_{\overline{x}} \mid x \in V(\phi)\}$ sont les seuls sommets $A$.

Pour chaque clause, dites $c = x \lor \overline{y} \lor z$, nous créons $b+1$ sommets bleus et trois sommets rouges supplémentaires $v_{x \in c},v_{\overline{y} \in c},v_{z \in c}$, tout en $B$. Laisser$v_x,v_{\overline{y}},v_z$ tous soient entièrement adjacents à la $b+1$ sommets bleus et connectez $v_x$ à $v_{x \in c}$, $v_y$ à $v_{\overline{y} \in c}$, et $v_z$ à $v_{z \in c}$.

Maintenant, puisque chaque gadget de clause a $b+1$les sommets bleus, nous savons qu'un ou trois littéraux de cette clause ont été inversés. Supposons que trois ont été inversés pour l'une des clauses. Mais nous utilisons au moins le budget$n + m + 2$.

Supposer que $\phi$ est une instance oui avec une affectation 1 sur 3 $\alpha: V(\phi) \to \{\top,\bot\}$. Retournez chaque sommet qui correspond à$\alpha$. Puisque chaque clause est satisfaite par exactement une variable, pour chaque clause il y a maintenant un sommet bleu, et pour chaque variable, exactement l'une d'entre elles est bleue, d'où nous avons$n + m = b$ sommets bleus.

Pål GD explique que le problème est NP-difficile, donc la prochaine étape est d'essayer de trouver des algorithmes raisonnables pour votre problème.

Je noterai que votre problème peut être réduit à MOT DE CODE DE POIDS MINIMUM: étant donné un code linéaire, trouvez un mot de code de poids minimum. Une autre façon d'énoncer ce problème est la suivante: étant donné une matrice booléenne$M$ et un vecteur booléen $y$, trouver un vecteur booléen non nul $x$ de telle sorte que le poids de Hamming $Mx \oplus y$est minimisé. (Toute l'arithmétique est effectuée modulo 2.) LE MOT DE CODE MINIMUM DE POIDS est connu pour être NP-dur, mais il existe certains algorithmes plus rapides que la force brute.

Voici la connexion. S'il y a$n$ sommets, puis tout $n$Le vecteur booléen -bit peut être considéré comme spécifiant quels sommets seront inversés par une opération de retournement particulière. Ainsi pour chaque sommet$v$ on obtient un flip-vector correspondant $m_v$. Mettez-les dans un$n \times n$matrice, où chaque ligne correspond à un vecteur de bascule différent. Laisser$y$ être un $n$vecteur booléen à deux bits qui spécifie les couleurs d'origine des sommets (bleu = 1, rouge = 0). Maintenant, le but est de trouver un vecteur booléen$x$ qui minimise le poids de Hamming $Mv \oplus y$. Un tel vecteur correspond immédiatement à un ensemble d'opérations de retournement qui minimise le nombre de sommets bleus dans le graphique.

Dans ce contexte, vous pourrez peut-être appliquer des algorithmes connus pour trouver des mots de code de poids minimum dans des codes linéaires à votre problème. Le temps d'exécution sera toujours exponentiel, mais plus rapide que d'essayer toutes les possibilités de$x$.