Le graphique 3-colorabilité est auto-réductible

Je m'intéresse à l'auto-réductibilité du problème du graphique 3-Coloralibity.

Définition du problème du graphique 3-Coloralibity.

Étant donné un graphe non orienté , existe-t-il un moyen de colorer les nœuds en rouge, vert et bleu afin qu'aucun nœud adjacent n'ait la même couleur? $G$

Définition de l'auto-réductibilité.

Un langage est auto-réductible s'il existe une machine de turing oracle TM telle que et pour toute entrée de longueur , interroge l'oracle pour des mots de longueur au plus . $L$ $T$ $L=L(T^L)$ $x$ $n$ $T^L(x)$ $n-1$

Je voudrais montrer de manière très stricte et formelle que la colorabilité du graphique 3 est auto-réductible.

La preuve de l'auto-réductibilité de SAT peut être utilisée comme exemple ( auto-réductibilité de SAT ).

À mon avis, l'idée générale de la preuve de l'auto-réductibilité du graphique 3-colorabilité est différente de la preuve de l'auto-réductibilité SAT à quelques égards.

SAT a deux choix pour chaque littéral (vrai ou faux) et la colorabilité du graphique 3 a trois choix (à savoir, rouge vert bleu).
Les choix de littéraux SAT sont indépendants les uns des autres et les choix de couleurs de la colorabilité du graphique 3 sont strictement dépendants, tout nœud adjacent doit avoir une couleur différente, cette propriété pourrait potentiellement aider à faire moins d'itération entre toutes les couleurs.

L'idée générale de la preuve .

Notons la couleur du sommet , qui peut prendre l'une des valeurs suivantes (rouge, vert, bleu). Définissez le graphe partir d'un graphe donné en coloriant le sommet arbitraire , affectez à' rouge 'et mettez le graphe avec le sommet coloré à l'entrée de l'oracle. Si oracle répond 1, ce qui signifie que le graphique modifié est toujours tricolore, enregistrez les affectations en cours et commencez une nouvelle itération, avec le sommet différent choisi arbitrairement, couleur sommet $c_{v_i}$ $v_i$ $G'$ $G$ $v_0$ $c_{v_0}$ $G'$ $v_0$ $v_1$ $v_1$ selon les couleurs des sommets adjacents. si oracle répond à 0, ce qui signifie que l'affectation précédente a cassé 3 colorabilité, choisissez une couleur différente dans l'ensemble des trois couleurs, mais toujours en fonction des couleurs des sommets adjacents.

La preuve précédente n'est pas mathématiquement robuste, la question est de savoir comment l'améliorer et la rendre plus formelle et mathématique stricte. Il semble que j'ai besoin de distinguer plus soigneusement les cas où le nouveau sommet n'a pas d'arêtes avec des sommets déjà colorés et lorsque le nouveau sommet est adjacent à des sommets déjà colorés.

De plus, je voudrais prouver que la colorabilité du graphique 3 est auto-réductible vers le bas.

Définition d'un langage auto-réductible vers le bas.

On dit que le langage est auto-réductible vers le bas s'il est possible de déterminer en temps polynomial si utilisant les résultats des requêtes les plus courtes. $A$ $x \in A$

L'idée semble simple et intuitive: commencez par colorier un sommet arbitraire, et à chaque itération ajoutez un sommet de couleur supplémentaire et vérifiez par oracle si le graphique est toujours tricolore, sinon inversez la coloration précédente et vérifiez une autre couleur.

Mais comment écrire la preuve de manière stricte et plus important comment trouver un encodage approprié d'un graphe.

En bref, je voudrais montrer que la colorabilité du graphique 3 est auto-réductible et auto-réductible vers le bas de manière stricte et formelle.

J'apprécierai partager vos pensées avec nous.

Mise à jour:

auto-réductibilité vers le bas

L'auto-réductibilité vers le bas est appliquée au problème de décision et son oracle répond au même problème de décision avec une entrée plus courte, à la fin du processus d'auto-réduction vers le bas, nous devrions avoir les bonnes affectations de couleurs.

Chaque graphe tricolore avec plus de trois sommets, a deux sommets de la même couleur. Apparemment, il n'y a que trois couleurs et plus de trois sommets, donc un certain nombre de sommets non adjacents peuvent avoir la même couleur. Si nous fusionnons et avec la même couleur que le résultat, nous avons toujours un graphique à 3 couleurs, simplement parce que, si le graphique est à 3 couleurs, il existe une affectation correcte de tous les sommets adjacents à et selon la même couleur de , donc en fusionnant $G$ $x,y$ $x$ $y$ $x$ $y$ $x, y$ $x, y$ nous n'avons pas besoin de changer la couleur des sommets, nous avons seulement besoin d'ajouter plus de bords entre les sommets déjà correctement colorés (je sais que ce n'est pas la meilleure explication, j'apprécierai si quelqu'un pourrait mieux l'expliquer). À chaque itération, nous prenons deux sommets non adjacents du graphe , fusionnons et et obtenons le graphe qui est notre entrée la plus courte dans l'oracle. Oracle répond s'il est tricolore ou non. Maintenant, le problème est avant de définir à l'entrée d'Oracle, je devrais colorer le sommet fusionné et tester la colorabilité de , si ce n'est pas en 3 couleurs, changez la couleur, mais comment l'implémenter correctement, j'ai besoin d'un bon codage pour cela. $x,y$ $G$ $x$ $y$ $G'$ $G'$ $G'$

auto-réductibilité

Tout d'abord, nous devons vérifier si un graphique donné est tricolore du tout, alors définissez-le sur l'entrée d'oracle, et oracle répondra s'il est tricolore - si oui, alors démarrez le processus. Deux sommets non adjacents peuvent avoir la même couleur dans un graphique à 3 couleurs. Le processus d'auto-réductibilité que nous devrions exécuter dans les itérations, je pense que nous pouvons commencer à partir du petit sous-graphe d'un graphe donné et à chaque itération ajouter un sommet de à $G$ $G'$ $G$ $G$ $G'$ . In paralel, we should maintain the assignment of already colored vertices. Unfortunately, I still don't get the idea completely. Would appreciate for help and hints.

complexity-theory reductions com
la source

just a note: I think that in the self-reduction you should use the "bare" version of the decision problem: the input of the decision problem is a graph and not a graph with some colored nodes. So you should modify the original graph to simulate a forced coloring of some nodes (and try to keep the instance shorter). In SAT this is easier because you just set the value of a variable and simplify the clauses.

Vor

What is the difference between self-reducibility and downward self-reducibility?

Yuval Filmus

@YuvalFilmus, set

S

$S$ is downward self-reducible if there exists a Cook-reduction of

S

$S$ to itself that makes queries that are each shorter than the reduction’s input (on input

x

$x$ the reduction makes the query

q

$q$ then

| q | < | x |

$|q| < |x|$ )

com

Whereas a set is self-reducible if ...?

Yuval Filmus

The search problem of any relation

R

$R$ is called self-reducible if it can be reduced to the decision problem of

S_{R}

$S_R$ .

com

As Vor mentions in his comment, your reduction doesn't work, since 3-colorability doesn't accept partial assignments of colors. The problem goes even deeper, since setting the color of a single vertex doesn't make any progress in determining whether the graph is 3-colorable: indeed, the graph is 3-colorable iff there is a 3-coloring in which vertex $v$ is assigned color $c$ , for any $v,c$ you choose.

Here is a hint on how to solve your exercise, second part. In any 3-coloring of a graph $G$ on more than three vertices, there are two vertices $x,y$ getting the same color (why?). If we merge $x$ and $y$ , the resulting graph is still 3-colorable (why?). Try to use this idea to construct a downward self-reducing algorithm for 3-colorability.

Edit: And here is a hint on how to solve the exercise, first part. Consider any two unconnected vertices $x,y$ . If there is a coloring in which they get the same color then $G_{xy}$ is 3-colorable (why?), and a coloring of $G$ can be extracted from a coloring of $G_{xy}$ (how?). When will this process stop?

Yuval Filmus
la source

Extra points if you can find a reduction which calls the oracle

O (1)

$O(1)$ times.

Yuval Filmus

Thank you very much for the hint, instead of partial coloring, we can use auxiliar graph

G^{'}

$G'$ and extend it accordingly to

G

$G$ . Graph

G

$G$ with more than three vertices have two vertices

x, y

$x, y$ with the same color, just because oracle answered that it's 3-colorable (but vertices are more than three), so there are should be vertices with the same color. But I don't get why the graph is still 3-colorable when we merge two vertices with the same color. On the other hand, why do we need to add edge between already colored vertices.

com

According to number of calls. In general, we can assign the same color to all not adjacent vertices, therefore in this case we don't have to ask oracle on every assignment (on the other hand, there are three colors, and it's crucial to take the right assignment. Seemingly correct assignment on

G^{'}

$G'$ , may become false on

G

$G$ ).

com

Suppose that a graph

G

$G$ has a 3-coloring

c

$c$ such that

c (x) = c (y)

$c(x) = c(y)$ . Now consider the graph

G_{x y}

$G_{xy}$ obtained by merging

x

$x$ and

y

$y$ . Can you find a 3-coloring for

G_{x y}

$G_{xy}$ ? How about the converse?

Yuval Filmus

Now that I understand the difference between self-reducibility and downward self-reducibility, I notice that my hint only makes sense for the latter. Added a different hint for the former. Perhaps that helps.

Yuval Filmus

Le graphique 3-colorabilité est auto-réductible

Réponses: