NP-problèmes difficiles sur les arbres

Plusieurs problèmes d'optimisation connus pour être NP-difficiles sur les graphes généraux peuvent être résolus de manière triviale en temps polynomial (certains même en temps linéaire) lorsque le graphe en entrée est un arbre. Les exemples incluent la couverture de vertex minimale, le jeu maximum indépendant, l'isomorphisme de sous-graphe. Nommez quelques problèmes d’optimisation naturels qui restent NP-difficiles sur les arbres.

Vous pouvez trouver des exemples "naturels" et "connus" de problèmes de graphes difficiles, même s'ils sont limités aux arbres de notre référence standard . Exemples:

• Flux intégral k- multi-commodité ,
• Sous-arbre intégré commun ,
• Sous-arbre commun .

(Celles-ci sont formulées comme des problèmes d’arborescence, mais vous pouvez les généraliser à des graphes arbitraires. Les formulations ci-dessus sont alors obtenues comme cas particulier lorsque vous limitez votre entrée aux arborescences.)

Une recette plus générale pour générer des problèmes difficiles sur les arbres: Prenez tout problème NP-difficile lié aux superséquences , aux superstrings , aux sous - chaînes , etc. Ensuite, réinterprétez une chaîne en tant que graphe de tracé étiqueté. Puis posez la question analogue pour les graphes généraux (sous-séquence graphe mineur, sous-chaîne sous-graphe). Et nous savons que le problème est NP-difficile même sur les arbres (et sur les chemins).

Il existe également de nombreux problèmes difficiles pour les étoiles pondérées, par réduction du problème des sous-ensembles. Un exemple naturel est:

• TSP avec deux voyageurs : à partir d’un graphe et d’une limite W pondérée aux arêtes , pouvons-nous trouver deux allées fermées C 1 et C 2 dans G telles que chaque allée ait un poids total au maximum égal à W et que chaque nœud de G soit recouvert en moins une promenade?$G$$W$$C_1$$C_2$$G$$W$$G$

Encore une fois, il est facile de proposer des variations du thème.

NP-complete a pour but de déterminer si un arbre peut être intégré à la grille d’entiers à deux dimensions, les sommets de l’arbre étant placés sur des points de grille distincts et les bords de l’arbre placés sur les bords de la grille.

Voir par exemple Gregori, IPL 1989 .

Le problème du groupe Steiner est un bel exemple. La contribution à ce problème est un graphe non orienté à graphe à pondération surfacique et k groupes de sommets S 1 , S 2 , … , S k . Le but est de trouver un arbre de poids minimum contenant au moins un sommet de chaque groupe. Il est facile de voir que le problème de Set Cover est un cas particulier même lorsque G est une étoile. Il est donc difficile d'approcher le problème à moins d'un facteur O ( log n ) à moins que P = NP. De plus, Halperin et Krauthgamer ont montré qu'il était difficile d'approcher le problème à moins d'un$G=(V,E)$$S_1, S_2, \ldots, S_k$$O(\log n)$ facteur pour tel ou fixe ε > 0 à moinsNP a randomisés algorithmes de temps quasi-polynomiale (voir le papier pour un énoncé précis). Il existe uneapproximation de O ( log 2 n ) sur les arbres de Garg, Konjevod et Ravi.$O(\log^{2-\epsilon} n)$$\epsilon > 0$$O(\log^2 n)$

L'un des problèmes les plus difficiles sur les arbres est le problème de bande passante minimale. Il est -Hard sur les arbres de degré maximum 3. En outre , il est NP-dur sur chenille circulaire de la longueur des cheveux 1.$NP$

Références:

Michael Garey, Ronald L. Graham, David S. Johnson et Donald E. Knuth. Résultats de la complexité pour la réduction de la bande passante. SIAM J. Appl. Math., 34 (3): 477 à 495, 1978.

Burkhard Monien. Le problème de la minimisation de la bande passante pour les chenilles avec une longueur de cheveux de 3 est NP-complete. SIAM J. Algebraic Discrete Methods, 7 (4): 505-512, 1986.

W. Unger. La complexité de l'approximation du problème de bande passante. Dans FOCS, pages 82–91, 1998

$G$$G$$k$$S$$k$$G$

Ce problème est NP-dur (et MAX SNP-dur) sur les étoiles [ 1 ].

[ 1 ] Garg, Vazirani et Yannakakis, Algorithmes d'approximation primal-double pour flux intégral et multicutures dans les arbres , Algorithmica, 18 (1), pages 3-20, 1997.

Le problème des pompiers a récemment fait l’objet de beaucoup d’attention et s’avère (quelque peu surprenant) très difficile à résoudre pour les arbres de degré maximum 3 . C'est en fait une question assez naturelle, décrite comme suit:

$k$

Ou une variante, également NP-difficile : existe-t-il une stratégie pour le pompier dans laquelle aucune feuille ne brûle?

Un problème qui, on pourrait le croire, ne serait PAS difficile pour les arbres, c’est le problème du gel des balises dans la géométrie de calcul : bref, le problème de la planification des réveils pour les robots commençant par un seul robot éveillé, où makespan est la mesure des coûts.

Il est connu pour être NP-difficile sur les graphes d'étoiles pondérées. Cependant, il reste à savoir si le problème est NP-difficile dans l'avion. On pourrait soutenir que la dureté NP ne provient pas de l'arborescence, mais de la métrique arbitraire, mais les graphes en étoile ne vous donnent qu'un espace limité de métriques.

$T$$V(T)$$k$$\phi: V(T)\to \{1,\ldots, k\}$$T$$i$$i+1$$K$$K$

$k$

La coloration Empire est NP-difficile pour les arbres.

$r$$s$$G$$r$$(s, r)$$s$$\text{COL}_r$$G$$s$

$s$$\text{COL}_r$$s \in \{3,\ldots, 2r − 1\}$$s$

Un flux dans un réseau est confluent s'il utilise au plus un arc sortant à chaque nœud. La dureté NP de la détermination d'un écoulement confluent maximal dans un arbre (de diamètre 4, avec plusieurs éviers autorisés) est prouvée dans: D. Dressler et M. Strehler, Flux confluents habilités: complexité et algorithmes, LNCS 6078 (2010) 347-358 .

$TS$$T$$T_1\in TS$$T$$T_1$$T$

Le problème est NP-difficile (en fait, il est difficile de faire une approximation) uniquement lorsque tous les arbres d’entrée ont un degré non borné.

Une coloration harmonieuse d'un graphique simple est une coloration de sommet appropriée, de sorte que chaque paire de couleurs apparaisse ensemble sur au plus un bord. Le nombre chromatique harmonieux d'un graphique est le plus petit nombre de couleurs dans une coloration harmonieuse du graphique. Edwards et McDiarmid ont montré que le problème de trouver le nombre chromatique harmonieux était NP-complet sur les arbres . En fait, ils montrent également que le problème reste NP-complet pour les arbres de rayon 3.

$u$$u$

Notez que dans le problème lié au TSP (et plus célèbre), l'objectif est de minimiser le maximum, plutôt que la latence moyenne. Je pense que le TRP est généralement considéré comme un problème plus compliqué (en fait, le TSP est dans P pour les métriques sur les arbres).

La dureté NP sur les arbres a été montrée dans RA Sitters "Le problème de latence minimum est NP-difficile pour les arbres pondérés", CITP 2002.

Le motif graphique est un problème NP-complet sur les arbres de degré maximum trois:

Fellows, Fertin, Hermelin et Vialette, limites de la traçabilité évidente pour la recherche de motifs connectés dans des graphes de couleur vertex Notes de cours en informatique, 2007, volume 4596/2007, 340-351

Il y a un problème (très général) que j'ai examiné dans le cadre d'un projet: une variante de ce problème reste NP-difficile même sur les graphiques à deux sommets et un seul bord, et une variante différente est NP-difficile sur les arbres. Puisque la dureté NP de la première variante ne découle évidemment pas de la forme du graphique, la seconde est probablement plus intéressante.

$S$$C$$G=(V,E)$$S \subset V$$C \subset V$$S \cap C = \emptyset$$s \in S$$|s|$$F$$f \in F$$|f|$$e \in E$$t_e$$R \subseteq C \times F$$(c,f) \in R$$c$$f$

$s \in S$$A_s$$\sum_{f \in A_s} |f| \leq |s|$$P_r$$G$$r = (c,f) \in R$$c$$s$$f \in A_s$$e$$D_e$$r = (c,f) \in D_e$$P_r$$e$$\sum_{(c,f) \in D_e}|f| \leq t_e$

Si vous ne souhaitez pas tous les téléchargements à routés mais essayez plutôt de maximiser la somme des filesizes des téléchargements qui sont routées , vous avez pouvez facilement réduire sous - ensemble somme à ce problème: vous avez un seul serveur avec de grandes quantités d'espace, une un seul client connecté au serveur avec une arête de capacité égale à la valeur cible de l'instance de sous-ensemble et pour chaque entier de l'instance de sous-ensemble, vous créez un fichier de taille égale; le client souhaite ensuite télécharger tous ces fichiers.

Une variante (beaucoup?) Plus intéressante pour cette question est le cas où vous essayez de minimiser le nombre d’arêtes dont la capacité est dépassée - peut-être que le réseau sur lequel nous travaillons modélise les câbles Internet transatlantiques et que le remplacement d’un câble est si coûteux que la différence en coût de mise à niveau à un facteur deux plus rapide et une mise à niveau à un facteur trois plus rapide est négligeable. Nous disons également que les emplacements des fichiers sur les serveurs sont déjà définis et ne peuvent pas être modifiés. Nous examinons donc uniquement les problèmes de routage.

$U$$S \subseteq P(U)$$u \in U$

$s \in S$$u \in s$$u$

L'idée est que le client a besoin de fichiers uniques pour tous les clusters de serveurs, de sorte que les arêtes reliant le client aux clusters de serveurs sont déjà à la limite de leurs capacités (leurs capacités sont 1, les fichiers ont une taille 1). Si le client télécharge des éléments de l'univers à partir de n'importe quel cluster, le bord qui se connecte à ce cluster est surchargé. Puisque nous avons seulement besoin de minimiser le nombrede surcharges (et non de combien nous dépassons les capacités), le client peut télécharger le reste des éléments de l’univers hébergé sur ce cluster de serveurs (donc le reste des éléments du sous-ensemble correspondant) sans pénalité. Cela correspond donc au sous-ensemble choisi. Le client souhaite télécharger tous les fichiers de l'univers une fois. Ainsi, l'univers sera effectivement couvert. Pour minimiser le nombre d'arêtes surchargées, nous devons minimiser le nombre de sous-ensembles choisis.

Notez que la construction ci-dessus génère un graphe d'arbre. Il s'agit donc d'un exemple de problème NP-difficile sur les arbres.

Le problème de flux non séparable. En fait, la PFE est difficile, même sur un seul bord (sac à dos).

$G(V, E)$$NP$

Formellement, le problème est le suivant:

ISOMORPHISME DE GRAPHE PARTITIONNÉ

$T = (V,E)$

$\{E1,E2 \}$$E$$T1 = (V,E1)$$T2 = (V,E2)$

La colonne NP-complétude cite le manuscrit non publié de Graham et Robinson, "Factorisation isomorphique IX: même les arbres".

DS Johnson, La colonne NP-complétude: un guide continu, Journal of Algorithms 3 (1982), 288–300

D'une certaine manière, j'ai raté le problème du nombre achromatique dans la dernière réponse, mais c'est l'un des problèmes les plus naturels que je connaisse, qui sont NP-complets sur les arbres.

La coloration complète d'un graphique est une coloration appropriée, de sorte qu'il existe un bord entre chaque paire de classes de couleurs. La coloration peut être définie contrairement à la coloration harmonieuse, comme une coloration appropriée telle que chaque paire de couleurs apparaisse sur au moins un bord. En outre, il peut être défini comme un homomorphisme complet (ou complet) à une clique. Le problème du nombre achromatique est un problème de maximisation , dans lequel nous cherchons le plus grand nombre de classes de couleurs dans une coloration complète du graphique.

Yannakakis et Gravil ont prouvé que ce problème posait un problème NP-difficile au complément des graphes bipartites . Cairnie et Edwards ont étendu ce résultat et ont montré que le problème est NP-complet sur les arbres .

Beaucoup de travail a été fait sur ce problème dans le domaine des algorithmes d'approximation [ 3 , 4 , 5 ].

$n$$k$$\lceil\frac{n}{k}\rceil$

Le circuit SAT est-il sur les arbres NPC?. Les sommets intérieurs des arbres sont étiquetés comme des portes OU / ET. Les feuilles sont des intrants. Déterminez s'il existe un ensemble d'entrées satisfaisantes que le circuit évaluera à True.

$2^k - 1$