Problèmes d'extensibilité difficiles

Dans le problème d'extensibilité, on nous donne une partie de la solution et nous voulons décider si nous pouvons l'étendre à une solution complète. Certains problèmes d'extensibilité peuvent être résolus efficacement tandis que d'autres problèmes d'extensibilité transforment un problème facile en un problème difficile.

Par exemple, le théorème de Konig-Hall déclare que tous les graphes bipartites cubiques sont colorables sur 3 arêtes mais la version d'extensibilité devient $NP$ -complète si l'on nous donne les couleurs de certaines arêtes.

Je recherche un document d'enquête sur les problèmes d'extensibilité difficiles où le problème de base est facile (ou trivial comme dans l'exemple ci-dessus).

cc.complexity-theory reference-request graph-theory np-hardness Mohammad Al-Turkistany
la source

Je ne sais pas s'il existe une enquête sur les problèmes d'extensibilité, mais au moins un problème très bien étudié est l' extension de précoloration . Vous trouverez de nombreux résultats à la recherche du nom du problème.

Juho

Deux remarques: 1) y a-t-il des problèmes de PNJ qui ne peuvent pas être transformés en un problème d'extension difficile? 2) Je pense qu'il serait très intéressant également une enquête qui se concentre uniquement sur les problèmes d'extensibilité, pour lesquels le problème "de base" a une complexité inconnue (par exemple le problème du rectangle monochromatique gratuit, ou certains jeux de puzzle)

Marzio De Biasi

@MarzioDeBiasi Commentaire très intéressant. 1) Je ne connais aucun exemple de ce genre. 2) GI est un bon candidat et je suppose que son problème d'extensibilité est NP-complet.

Mohammad Al-Turkistany

La version d'extension des problèmes NP-hard est NP-hard (effectuez une recherche gourmande de certificat à l'aide d'Oracle).

Kaveh

@MarzioDeBiasi: L'extensibilité GI est en effet GI-complète (pas seulement GI-difficile, ce que vous vouliez dire, je crois), et donc pas NP-complète à moins que le PH ne s'effondre. L'extensibilité de l'IG peut être reformulée sous forme d'IG de couleur vertex (où les sommets d'une couleur donnée ne peuvent être mappés qu'aux sommets de la même couleur), ce qui se réduit à l'IG de plusieurs façons (dont l'une consiste à attacher des gadgets aux sommets, similaire à votre idée

K_{n}

$K_n$

Joshua Grochow

n-colorier le graphique nxn Sudoku est trivial, mais si certaines des couleurs vous sont données (la version d'extensibilité), il devient NP-complet.

Par le "graphique Sudoku", j'entends le graphique naturel dont le problème de coloration associé est le Sudoku. À savoir, supposons que est un carré. Le graphe aura sommets, que nous noterons pour $n=k^2$ $n^2$ $(r_1, r_2; c_1, c_2)$ . Pour chaque fixe, les sommetsforment une-clique; pour chaque fixeles sommetsforment une-clique; et pour chaque fixe $r_1,r_2,c_1,c_2 \in [k] = [\sqrt{n}]$ $(r_1,r_2)$ $(r_1, r_2; *, *)$ $n$ $(c_1, c_2)$ $(*, *; c_1, c_2)$ $n$ , les sommets forment une -clique. $(r_1, c_1)$ $(r_1, *; c_1, *)$ $n$

Joshua Grochow
la source

Problèmes d'extensibilité difficiles

Réponses: