NP-complétude

[Ceubex]

Bonjour,

On définie le problème K-part comme ceci :
Données : un graphe G=(X,A)
Question : existe-t-il une partition de X en K sous ensembles X1, X2... tels que tous ces sont graphes soient complets (possèdes toutes les arrêtes possibles)

On admet que 3-part est NP-complet, démontrer à partir de 3-Par que 4-Part est NP-complet.

Alors on prouver que 4-Part est NP pas de problème mais après pour trouver la bonne instance et montrer la conservation de la réponse je ne m'en sors pas

Pouvez-vous m'aider ?
Merci

[Doraki]

Pour chaque problème 3-part, donc pour chaque graphe G,
il faut construire un graphe G' tel que le problème 4-part pour G' équivaut au problème 3-part de G :
G partitionnable en 3 parties complètes <=> G' partitionnable en 4 parties complètes.

Faut vraiment pas chercher très loin pour avoir une construction qui marche.

[Ceubex]

Pour chaque problème 3-part, donc pour chaque graphe G,
il faut construire un graphe G' tel que le problème 4-part pour G' équivaut au problème 3-part de G :
G partitionnable en 3 parties complètes G' partitionnable en 4 parties complètes.

Faut vraiment pas chercher très loin pour avoir une construction qui marche.

Merci pour ta réponse mais j'avais déjà compris cela en fait. Tu prend par exemple un sommet isolé et tu as tout de suite G partitionnable en 3 parties complètes => G' partitionnable en 4 parties complètes. Ce qui m'ennuit plus c'est la réciproque car si le peut partitionner G' en 4 parties complètes rien ne me dit comment obtenir un graphe G à partir de là partitionnable en 3 parties complètes

[lapras]

Le sommet isolé tu le rajoutes à G ? Si oui je ne vois pas ton problème...

[Doraki]

Je vois pas où t'as besoin de construire un graphe G à partir d'un graphe G'.

La réciproque que tu dois montrer c'est "si le G' qu'on a construit à partir de G peut être décomposé en 4, alors G peut être décomposé en 3".

[Ceubex]

Je vois pas où t'as besoin de construire un graphe G à partir d'un graphe G'.

La réciproque que tu dois montrer c'est "si le G' qu'on a construit à partir de G peut être décomposé en 4, alors G peut être décomposé en 3".

Ca n'est pas tout à fait la réciproque ça, je crois. C'est j'ai un graphe G' "quelconque" qui n'a de particulier que le fait d'avoir 4 partitions complètes. Imaginons que G' soit un graphe composé de 4 paires de sommets. Les sommets d'une paires sont connectés entre eux mais les paires de sommets ne sont pas connectées entre elles. On a bien un graphe en 4 partition mais on ne peut pas en tirer 3.

[Doraki]

Ben non tu n'as pas bien compris comment on fait des réductions.

Il s'agit de réduire le problème 3-part dans le problème 4-part, c'est-à-dire trouver un algorithme qui transforme une instance quelconque de 3-part G en une instance de 4-part G' qui a la même réponse.

On demande pour chaque graphe G, de construire un graphe G' tel que
- si G est séparable en 3 sous-graphes complets, alors G' est séparable en 4-sous-graphes complets
- si G n'est pas séparable en 3 sous-graphes complets, alors G' n'est pas séparable en 4-sous-graphes complets.

Une fois que t'as fait ça t'as montré que 4-part est au moins aussi difficile à résoudre que 3-part.

A aucun moment on te demande de montrer qu'il y a réduction dans le sens inverse, de 4-part dans 3-part, ni de déduire quoi que ce soit sur un graphe G' quelconque vérifiant ou non 4-part.