Problèmes faciles sur les graphiques non pondérés, mais difficiles pour les graphiques pondérés

De nombreux problèmes de graphes algorithmiques peuvent être résolus en temps polynomial à la fois sur des graphes non pondérés et pondérés. Quelques exemples: chemin le plus court, arbre couvrant minimum, chemin le plus long (dans les graphiques acycliques dirigés), débit maximal, coupe minimale, correspondance maximale, arborescence optimale, certains problèmes de sous-graphe les plus denses, coupes dirigées disjointes maximales, clique maximale dans certaines classes de graphiques, indépendante maximale définir dans certaines classes de graphes, divers problèmes de chemin disjoint max, etc.

Il existe cependant certains problèmes (bien que probablement beaucoup moins) qui peuvent être résolus en temps polynomial dans le cas non pondéré , mais qui deviennent difficiles (ou ont un statut ouvert) dans le cas pondéré . Voici deux exemples:

1. Étant donné le graphe complet -vertex et un entier , trouvez un sous-graphe connecté s'étendant sur le plus grand nombre possible d'arêtes. Ceci est résoluble en temps polynomial, en utilisant un théorème de F. Harary, qui raconte la structure des graphes optimaux. D'un autre côté, si les bords sont pondérés, la recherche du sous-graphique couvrant le poids minimal est difficile.k ≥ 1 k k N $n$$k\geq 1$$k$$k$$NP$

2. Un article récent (décembre 2012) de S. Chechik, MP Johnson, M. Parter et D. Peleg (voir http://arxiv.org/pdf/1212.6176v1.pdf ) considère, entre autres, un problème de chemin qu'ils appelez le chemin d'exposition minimum. Ici, on cherche un chemin entre deux nœuds spécifiés, tel que le nombre de nœuds sur le chemin, plus le nombre de nœuds qui ont un voisin sur le chemin est minimum. Ils prouvent que dans les graphiques de degrés bornés, cela peut être résolu en temps polynomial pour le cas non pondéré, mais devient dur dans le cas pondéré, même avec le degré lié 4. (Remarque: La référence a été trouvée comme réponse à la question Qu'est-ce que la complexité de ce problème de chemin? )$NP$

Quels sont les autres problèmes intéressants de cette nature, c'est-à-dire lorsque le passage à la version pondérée provoque un "saut de complexité"?

Dans le monde des algorithmes d'approximation, il y a le problème de la couverture des sommets capacités. Étant donné et les capacités entières c ( v ) pour chaque v ∈ V, le but est de trouver une couverture de sommet de taille minimale pour G où le nombre d'arêtes couvertes par v est au plus c ( v ) . Ce problème a une approximation de facteur constant dans le cas non pondéré (c'est-à-dire que nous voulons minimiser la taille de la couverture des sommets) alors qu'il est Ω ( log n ) -hard (sauf$G=(V,E)$$c(v)$$v \in V$$G$$v$$c(v)$$\Omega(\log n)$ ) dans le cas pondéré (chaque sommet a un poids w ( v ) et nous voulons minimiser le poids de la couverture).$P = NP$$w(v)$

Mon exemple préféré est le problème de domination indépendante (étant donné le graphique et l'entier k , G a-t-il un ensemble indépendant maximal d'inclusion d'au plus k sommets?). Par un joli résultat dû à Martin Farber ( voir ici ), la version non pondérée est solvable polynomialement dans les graphes d'accords. Gerard Chang prouve que la version pondérée est NP-complète pour les graphes d'accords ( voir ici ).$G$$k$$G$$k$

Le problème de correspondance parfaite dans les graphiques bipartites est en tandis que la correspondance parfaite de poids exact du graphique bipartite est N P -Complet .$P$$NP$

À la suite de la réponse de Mohammad Al-Turkistany, il semble que bon nombre des problèmes non pondérés résolubles en temps polynomial pourraient être rendus complets dans le cas pondéré, si nous demandons s'il existe une solution qui a exactement un poids donné. La raison en est que cela peut permettre de coder le problème de somme de sous-ensemble dans la tâche considérée.$NP$

Par exemple, dans le cas de la correspondance parfaite de poids exact, nous pouvons prendre un graphique bipartite complet en entrée, en attribuant des poids donnés aux bords d'une correspondance particulière et un poids de 0 à tous les autres bords. Il est facile de voir que ce graphique pondéré a une correspondance parfaite de poids exactement si et seulement s'il y a un sous - ensemble des poids qui sommes exactement à W . (S'il existe un tel sous-ensemble, alors nous pouvons prendre les bords correspondants de la correspondance fixe et l'étendre à une correspondance parfaite avec des bords de poids 0, en utilisant cela comme un graphique bipartite complet.) Je pense, une astuce simple similaire peut également fonctionner pour un certain nombre d'autres problèmes.$W$$W$

L'équilibrage des graphes (également connu sous le nom d'Orientation Min-degré) est un autre exemple de ce phénomène. Dans ce problème, on nous donne un graphique pondéré sur les bords non orienté. Le but est d'orienter les bords de sorte que le degré extérieur maximal (pondéré) du digraphe résultant soit minimisé.

Le problème est souvent motivé par un scénario de planification. Imaginez que chaque sommet est un processeur et chaque bord est un travail qui n'est autorisé à s'exécuter que sur l'un de ses deux points de terminaison. Le poids d'un bord est la longueur du travail correspondant et l'objectif est de minimiser la durée de fabrication.

Le problème est NP-hard et APX-hard, même si tous les poids sont 1 ou 2 (voir Ebenlendr et al. Il est cependant dans P pour les graphiques non pondérés (voir Asahiro et al. "Classes de graphiques et la complexité de l'orientation des graphiques minimisant le degré de pondération maximal" dans CATS 2008).

Ce n'est peut-être qu'un exemple trivial et vous pouvez le considérer comme un cas dégénéré, mais le premier exemple qui m'est venu à l'esprit est le problème du voyageur de commerce (où l'on suppose généralement que le graphique est complet). Notez que la version non pondérée est le cycle hamiltonien, ce qui est trivial pour les graphiques complets.

Trouver le chemin de coût minimum sous contrainte de retard (alias le problème du chemin le plus court contraint) semble correspondre ici.

$G=(V,E)$$d:V\to\mathbb {N}^+$$c:\to\mathbb {N}^+$$D\in \mathbb {N}^+$$s,t\in V$

$s-t$$D$

$\forall v\in V:d(v) =1$$hop-count$

Si le problème est pondéré, il devient le chemin le plus court contraint , qui est connu pour être NP-complet même sur les DAG.

Le problème local Max Cut avec le voisinage FLIP est PLS-complet dans les graphiques généraux pondérés entiers.

AA Schaeffer et M. Yannakakis. (1991). Problèmes de recherche locale simples et difficiles à résoudre. SIAM Journal on Computing, 20 (1): 56-87.

Cependant, si le poids le plus important est polynomial dans la taille du graphique, les améliorations locales du potentiel (poids d'une coupe) convergeront en temps polynomial, car chaque amélioration augmentera la fonction potentielle d'au moins un, et la fonction potentielle est borné polynomialement. (Avec des poids généraux, trouver une solution accessible par des améliorations locales à partir d'une coupe de départ spécifique est PSPACE-complete.)

Une chose similaire se produit également dans d'autres "jeux potentiels".

Le vendeur itinérant est ouvert sur les graphiques de grille vendus, mais le cycle de Hamilton (la variante non pondérée) est connu pour être polynomial.

Discussion des deux sur le projet de problèmes ouverts:

http://cs.smith.edu/~orourke/TOPP/P54.html

Sur 2K_1-free La coupe maximale est polynomiale et la coupe maximale pondérée est NP-complète.