Complexité paramétrée de P à NP-dur et retour

Je cherche des exemples de problèmes paramétrés par un nombre , où la dureté du problème est non monotone en . La plupart des problèmes (selon mon expérience) ont une transition de phase unique, par exemple -SAT a une transition de phase unique de (où le problème est en P) à (où le le problème est NP-complet). Je m'intéresse aux problèmes où il y a des transitions de phase dans les deux sens (de facile à difficile et vice-versa) lorsque augmente.$k \in \mathbb{N}$k k ∈ { 1 , 2 } k ≥ 3 $k$$k$$k \in \{1,2\}$$k \ge 3$$k$

Ma question est un peu similaire à celle posée lors de Hardness Jumps in Computational Compality , et certaines des réponses fournies sont pertinentes pour ma question.

Exemples dont je suis au courant:

1. k = $k$ colorabilité des graphes plans: En P sauf lorsque , où il est NP-complet.$k=3$
2. Arbre de Steiner avec terminaux: dans P lorsque (s'effondre au plus court chemin - ) et lorsque (se réduit au MST), mais NP-dur "entre". Je ne sais pas si ces transitions de phase sont précises (par exemple, P pour mais NP-difficile pour ). De plus, les transitions de dépendent de la taille de l'instance d'entrée, contrairement à mes autres exemples.k = 2 s t k = n k 0 k 0 + 1 $k$$k=2$$s$$t$$k=n$$k_0$$k_0+1$$k$
3. Compter les assignations satisfaisantes d’une formule planaire modulo : Dans P lorsque est un nombre premier de Mersenne , et # P-complet pour la plupart (?) / Toutes les autres valeurs de (de Aaron Sterling dans ce fil de discussion) ). Beaucoup de transitions de phase!n n = 2 k - 1 $n$$n$$n=2^k-1$$n$
4. Détection de sous-graphe induite: le problème n'est pas paramétré par un entier mais par un graphe. Il existe des graphes (où désigne un certain type de relation de sous-graphe), pour lequel déterminer si pour un graphe donné est dans P pour mais NP-complet pour . (de Hsien-Chih Chang dans le même fil ). ⊆ H i ⊆ G G i ∈ { 1 , 3 } i = $H_1 \subseteq H_2 \subseteq H_3$$\subseteq$$H_i \subseteq G$$G$$i\in \{1,3\}$$i=2$

Les tests de propriétés sont un domaine où la complexité des problèmes est non monotonique. Soit l'ensemble de tous les graphes vertex et appelons une propriété de graphe. Un problème générique consiste à déterminer si un graphe a la propriété (c'est-à-dire ) ou est loin d'avoir la propriété dans un sens. En fonction de ce que est et du type d'accès aux requêtes que vous avez sur le graphique, le problème peut être assez difficile. nP⊆ G n GPG∈PP$\mathcal{G}_n$$n$$P \subseteq \mathcal{G}_n$$G$$P$$G \in P$$P$$P$

Mais il est facile de voir que le problème est non monotone, en ce sens que si nous avons , le fait que soit facilement testable n'implique pas que soit facilement testable ou que est. P S $S \subset P \subset T$$P$$S$$T$

Pour voir cela, il suffit d'observer que et sont tous deux trivialement testables, mais que, pour certaines propriétés, il existe des limites inférieures fortes. P = $P = \mathcal{G}_n$$P = \emptyset$

Pour un graphe donné et un entier , la ième puissance de , notée , a le même sommet défini de sorte que deux sommets distincts sont adjacents dans si leur distance dans est égale à la plupart des . Le problème de la puissance th du graphe divisé demande si un graphe donné est la puissance th d'un graphe scindé.k ≥ 1 k G G k G k G k k $G$$k\ge 1$$k$$G$$G^k$$G^k$$G$$k$$k$$k$

• Pour , le problème peut être résolu en temps linéaire. Cela est dû au fait que la reconnaissance des graphiques fractionnés est réalisable en temps linéaire (bien connue).$k=1$
• Pour , le problème est NP-complet. Ceci est prouvé par Lau et Corneil dans Reconnaître les puissances des graphes d'intervalle, de division et d'accords appropriés , SIAM J. Discrete Math., 18 (2004), 83-102 .$k=2$
• Pour , le problème est trivial: seuls les graphes complets sont les ème puissances d'un graphe divisé.$k\ge 3$$k$

L'un de ces problèmes est la coloration des contours des graphes plans où le paramètre est - degré maximal d'un graphe. Lorsque ou il existe des algorithmes exacts polynomiaux connus ( voir ici ), alors que pour ces algorithmes ne sont pas connus et qu'il n'y a pas de preuves de dureté NP pour ces cas. .$\Delta$$\Delta=2$$\Delta\geqslant 7$$3\leqslant\Delta\leqslant 6$

La question connexe est discutée ici .

Déterminer si un graphique a une clique dominante pour:$G$

• $diam(G)=1$ est trivial - la réponse est toujours 'oui'
• $diam(G)=2$ est NP-complet
• $diam(G)=3$ est NP-complet
• $diam(G)\ge 4$ est trivial - la réponse est toujours "non"

Le cas est dû à Brandstädt et Kratsch et le cas est noté dans un de mes articles récents .$diam(G)=3$$diam(G)=2$

Est-ce un exemple du phénomène que vous recherchez?

Considérons le problème de k-Clique, où k est la taille de la clique que nous recherchons. Le problème est donc "Existe-t-il une clique de taille k dans le graphe G sur n sommets?"

Pour toutes les constantes k, le problème est dans P. (L'algorithme de force brute s'exécute dans le temps .) Pour les grandes valeurs de k, par exemple les valeurs telles que n / 2, il est NP-complet. Lorsque k devient très proche de n, comme nc pour une constante constante, le problème se retrouve dans P car nous pouvons rechercher dans tous les sous-ensembles de n sommets de taille nc et vérifier si l'un d'entre eux forme une clique. (Il n'y a que tels sous-ensembles, ce qui est polynomial quand c est une constante.)O ( n c$O(n^k)$$O(n^c)$

Voici un exemple qui pourrait être du type que vous recherchez. Le paramètre n'est pas un entier, c'est une paire de nombres. (Bien que l’un d’eux puisse être corrigé pour en faire un problème à un paramètre.)

Le problème consiste à évaluer le polynôme de Tutte d’un graphe G aux coordonnées (x, y). Nous pouvons restreindre les coordonnées à des entiers. Le problème est dans P si (x, y) est l’un des points (1, 1), (-1, -1), (0, -1), (-1,0), ou satisfait (x-1 ) (y-1) = 1. Sinon, c'est # P-dur.

Je viens de l'article de Wikipedia sur le polynôme de Tutte .

Qu'en est-il de la question du calcul du permanent d'une matrice modulo ? Pour cela est facile (puisque permanent = déterminant), et Valiant (dans " La complexité du calcul du permanent ") a montré qu'il peut être calculé modulo dans le temps pour par une variante modifiée de l’élimination gaussienne. Mais pour qui n’est pas une puissance de , c’est UP-Hard. k = 2 2 d O ( n 4 d - 3 ) d ≥ 2 k $k$$k=2$$2^d$$O(n^{4d-3})$$d \geq 2$$k$$2$

Un autre problème avec ce phénomène est le problème MINIMUM -SPANNER sur les graphes fractionnés.$t$

Pour une constante , une clé d'un graphe connexe est un sous-graphe connexe de tel que pour chaque paire de sommets et , la distance entre et dans soit au plus fois leur distance dans . Le minimum problème de -SPANNER demande un -spanner avec un nombre minimum d'arêtes d'un graphe donné.t G H G x y x y H t G t $t$$t$$G$$H$$G$$x$$y$$x$$y$$H$$t$$G$$t$$t$

Un graphe divisé est un graphe dont le sommet peut être partitionné en une clique et un ensemble indépendant.

Dans cet article, il a été montré que MINIMUM 2-SPANNER sur les graphes fractionnés est NP-difficile tandis que pour chaque , MINIMUM SPANNER est facile sur les graphes fractionnés.$t \ge 3$$t$

Exemple bien connu est -edge coloration.$k$

Il est décidable en temps polynomial si sinon il est complet .N P$k \ne \Delta$$NP$

Pour les graphes cubiques, déterminer l’existence d’une coloration des contours en utilisant:

• $k=2$ couleurs est trivial puisque la réponse est toujours non.
• N $k=3$ couleurs est complète$NP$
• $k \ge 4$ couleurs est trivial puisque la réponse est toujours oui.

Holyer, Ian (1981), "La NP-complétude de la coloration des bords", SIAM Journal on Computing 10: 718–720

http://en.wikipedia.org/wiki/Edge_coloring

Ceci est un exemple intéressant (et surprenant) pour une transition de phase de P NP-difficile P NP-difficile :$\to$$\to$$\to$$\to \cdots$

Décider si un graphe complet sur sommets, dans lequel chaque sommet a un classement strict de tous les autres sommets, admet qu'une correspondance courante se trouve dans P pour impairs et NP-difficile pour pair . (Le paramètre est le nombre de sommets .)$n$$n$$n$$n$

La preuve a été annoncée dans cet article .

Un chemin dans un graphique de couleur marginale est arc-en - ciel si aucune couleur n'y apparaît deux fois. Un graphique est coloré en arc -en- ciel s'il y a un chemin en arc-en-ciel entre chaque paire de sommets. Soit RAINBOW - COLORABILITE, le problème de décider si un graphe donné peut être coloré en arc-en-ciel en utilisant couleurs.$k$$k$

Pour tout graphe , le problème est facile pour car cela équivaut à vérifier si est un graphe complet. Pour les graphes scindés , le problème est -complete pour et pour toutes les autres valeurs de .k = 1 G N P k ∈ { 2 , 3 } P $G$$k=1$$G$$\sf NP$$k \in \{2,3\}$$\sf P$$k$

Voir Chandran, L. Sunil, Deepak Rajendraprasad et Marek Tesař. "Coloration arc-en-ciel des graphiques fractionnés." Préimpression arXiv arXiv: 1404.4478 (2014).

Un sous-ensemble d'un graphe est un cutset déconnecté si et sont déconnectés.G G [ U ] G - $U\subseteq V(G)$$G$$G[U]$$G-U$

Décider si un graphe de diamètre 1 a un cutset déconnecté est trivial. Le problème devient NP-difficile sur les graphes de diamètre 2 voir ce document et est à nouveau facile sur les graphes de diamètre au moins 3 voir ce papier .