Super Mario coule dans NP?

Une extension classique du problème du débit maximal est le problème du "débit maximal dans le temps": on vous donne un digraphe, dont deux nœuds sont distingués comme source et puits, où chaque arc a deux paramètres, une capacité par -unité et un délai. Vous avez également un horizon de temps . L'objectif est de calculer un débit au fil du temps qui obtient le montant maximum de matériel de la source vers le puits par le temps . Un débit de valeur maximale peut être calculé en temps polynomial par une réduction classique astucieuse au débit max à coût min. $T$ $T$

Je suis intéressé par une extension de ce modèle où les arêtes ont un troisième paramètre "durée de vie". Si un arc a une durée de vie , et est le premier moment auquel un flux positif est envoyé à travers l'arc, alors nous détruisons l'arc au temps . Vous pouvez penser à cela comme aux plates-formes de Super Mario Brothers qui tombent / sont détruites peu de temps après avoir marché dessus, ou vous pouvez les considérer comme des batteries nécessaires pour alimenter les bords, qui ne peuvent pas être éteintes après leur allumage . ( Modifier :) Le problème de décision est, lorsqu'on lui donne également une borne inférieure de valeur de flux , si l'on peut planifier un flux respectant à la fois la borne supérieure d'horizon temporel et la borne inférieure de valeur de flux. $\ell$ $t$ $t+\ell$ $B$

Jusqu'à présent, je peux voir que ce problème est fortement NP-difficile (via 3 partitions). Mais, je ne sais pas vraiment si c'est en NP: y a-t-il une garantie d'une manière d'exprimer une solution de manière compacte? Dans la version classique, un type spécial d'écoulement optimal est utilisé pour contourner ce problème.

Remarque: le modèle ci-dessus est un peu sous-spécifié, car vous pouvez autoriser ou interdire le stockage de flux aux nœuds, et vous pouvez avoir un modèle temporel discret ou continu. La résolution de la question pour l'un de ces modèles serait excellente.

ds.algorithms graph-algorithms network-modeling max-flow-min-cut daveagp
la source

Je ne suis pas sûr de comprendre. Pourquoi y a-t-il un problème à exprimer un plan d'écoulement particulier de manière compacte et à vérifier que le débit total est au moins F en temps poly?

Suresh Venkat

Vous pensez peut-être à la façon de prouver que la sortie d'un problème d'optimisation, dont la sortie est un flux temporisé, peut être vérifiée pour l'optimalité dans le temps poly. Cependant, souvent, on montre que les problèmes de décision avec seulement des réponses oui / non sont dans NP, et les problèmes d'optimisation qui maximisent certaines fonctions comme le flux sont généralement transformés en problème de décision en ajoutant une valeur de borne inférieure B à l'entrée, et le problème de décision devient "Existe-t-il une solution avec une valeur au moins B?"

andy_fingerhut

Suresh: disons que dans le modèle discret, la façon naturelle d'exprimer un plan d'écoulement prend entiers pour chaque arc, mais ce n'est pas polynomial, c'est seulement pseudo-polynomial dans la taille d'entrée. De même, dans le modèle continu, je ne vois pas comment compresser cela.

T

$T$

daveagp

Andy: Vous avez raison, en termes formels, il vaut mieux que j'énonce cela comme un problème de décision en ayant une valeur inférieure en plus d'un horizon temporel, alors c'est quelque chose pour lequel nous pourrions demander s'il se situe dans NP.

daveagp

@daveagp: Avez-vous essayé la dureté PSPACE, par exemple en réduisant QBF à votre problème?

Yoshio Okamoto

Réponses:

Cela fait longtemps mais je suis sûr que ce problème est en P.

J'ai écrit ma thèse de doctorat à ce sujet en 1995. Voir "Algorithmes de flux de réseaux dynamiques efficaces" par Bruce Hoppe soumis au département de Cornell CS. En ligne à http://dspace.library.cornell.edu/bitstream/1813/7181/1/95-1524.pdf

Voir Chapitre 8 "Extensions" section 8.1 sur les "bords mortels"

Bruce Hoppe
la source

"C'était une nuit sombre et orageuse. Jack était immobile dans sa cabine - immobile à l'exception de son estomac, qui tournoyait dans ses tripes comme un tour de carnaval fou ..." (page xiii, où l'auteur discute des applications pratiques).

Neal Young

Belle citation, Neal! :) BTW daveagp fait un bon point sur la nécessité d'avoir un espace pseudo-polynomial pour stocker le "flux" qui répond à la question de décision. Comment non seulement trouver un flux optimal mais aussi représenter ce flux en P est les chapitres 1-7 de ma thèse

Bruce Hoppe

Excellent! J'ai enfin lu tout ça. Une fois que nous avons corrigé le premier flux de temps atteint un bord, la preuve de la faisabilité du réseau avec les heures de début et de fin résultantes est en P (en supposant que le maintien est autorisé), et donc le problème d'origine est en NP: notre certificat de taille polynomiale répertorie l'heure de début pour chaque bord. Super Mario coule donc NP-complètement. Questions aléatoires: l'interdiction de la conservation change-t-elle quelque chose? existe-t-il un algorithme d'approximation décent?

daveagp

EDIT: la réponse est FAUX. J'ai fait l'hypothèse (idiote) implicite que lorsqu'un flux de chemin commence au temps s et se termine au temps t et passe par le bord e, il bloque le bord e pendant cette durée. Cependant, ce n'est pas vrai. Voir *.

Remarque: cette approche est peut-être inutilement compliquée ou incorrecte. Bien que j'aie essayé de le vérifier et de l'écrire attentivement - je n'y ai pas passé énormément de temps.

En supposant que le «stockage» n'est pas autorisé, par exemple, le flux doit être transféré immédiatement. Soit le nombre d'arêtes et la longueur d'entrée. Je n'ai pas précisé de temps continu ou discret, car je ne l'ai pas pris en considération. Cela devrait fonctionner pour une pensée discrète, pour une continuité, j'en suis sûr. $m$ $N$

Ensuite, nous pouvons décrire la solution comme un ensemble de "chemins-flux" de la source au puits. Un flux de chemin est un quadruple qui se compose des éléments suivants: Un chemin simple de la source au puits; Heure de début du trajet-flux ; Quantité de flux à travers le chemin ; Débit . $(P,s,a,r)$ $P$ $s$ $a$ $r$

Soit une solution donnée par un ensemble d'écoulements. Nous pouvons vérifier si la solution donnée par ces trajets est correcte dans le polynôme temporel danset : $F$ $|F|$ $N$

Pour chaque front et un instant , additionnez le débit de tous les trajets passant par au temps . Chaque flux de chemin a une heure de début et de fin, il nous suffit donc de considérer les moments où un flux de chemin commence ou se termine (entre ces moments, rien ne change en ce qui concerne les flux de chemin qui dépassent le bord . $e$ $t$ $e$ $t$ $e$
Pour chaque chemin d'écoulement , nous pouvons vérifier si le flux est tout ce qu'il arrive à l'évier avant que le temps . $T$
Pour chaque bord, nous pouvons vérifier si un flux de chemin passe après qu'il a été détruit ou non.
La borne inférieure du flux nous pouvons simplement vérifier, en additionnant les quantités de flux des voies d'écoulement. $B$

Maintenant, nous avons besoin de « juste » pour montrer que le nombre de flux chemin est polynomiale en . $N$

Pour une solution donnée, nous pouvons déterminer le moment où un flux a traversé un bord et quand le bord a été détruit. Convertissez cela en un problème avec une solution équivalente: il y a des limites strictes sur chaque bord quand il peut être utilisé et quand il ne l'est pas - une heure de début et de fin. Soit l'ensemble de tous ces temps. $\{t_1,...,t_k\}$

Considérons une solution non compacte et (initialement) un ensemble vide de flux de chemin. L'idée est que nous trouvons de manière itérative un chemin-flux dans la solution non compacte, le supprimons et le stockons dans notre ensemble de chemins-flux.

Trouvez les flux de chemin qui commencent et se terminent entre et , mais ne se terminent pas entre et tels que . Soit l'ensemble des flux de chemin entre et avec les propriétés décrites ci-dessus. $t_i$ $t_j$ $i<j$ $t_p$ $t_q$ $[t_p,t_q] \subseteq [t_i,t_j]$ $F_{i,j}$ $t_j$ $t_j$

Supposons que nous avons déjà supprimé tous les flux de chemin pour tous les intervalles plus petits que . Trouvez avec gourmandise les flux qui commencent et se terminent en $[i,j]$ $[t_i,t_j]$ $[t_{i+1},t_{j-1}]$ $|F_{s,t}| \leq m$

$F_{t_i,t_j}$ $t_{i+1}$ $t_{j-1}$

$\sum_{i,j \in [k]} | F_{i,j} |\leq c m^3$ $c$

Ruub
la source

Pour moi, la borne de décomposition semble défectueuse, je vais essayer de donner un contre-exemple illustratif. Supposons que le réseau ne soit qu'une source -> bord descendant de la capacité 100, retard 0, durée de vie 100. Considérons maintenant ce schéma de flux: dans l'intervalle de temps [0, 1) envoie le flux à un taux de 1; dans [1, 2) à un taux de 2, etc. jusqu'à un taux de 100 dans [99, 100). Toute décomposition nécessite> = 100 chemins-flux qui contredit votre affirmation telle que je la comprends. Je dois mentionner que Ford et Fulkerson évitent cet obstacle dans leur solution classique (sans durée de vie) en envisageant un type spécifique de solution optimale, pas arbitraire.

daveagp

Cela peut probablement être évité en maximisant également la «durée de vie» du flux, mais il y a un autre problème dans la preuve, je l'ai édité pour le clarifier.

Ruub

D'après ce que je comprends, vous ne devriez stocker qu'un seul nombre par arc, représentant l'instant auquel le flux commence à être envoyé à travers l'arc. Cela suppose qu'après cela, l'arc est rendu inutilisable. Si, dans le cas contraire, l'arc peut être réutilisé après avoir cessé d'être utilisé, il devrait avoir des solutions arbitrairement proches des solutions au débit maximal au fil du temps (car le débit pourrait cesser d'être envoyé pendant une durée arbitrairement petite, puis recommencer à être pompé à nouveau ).

Leandro M.
la source

Je ne peux pas comprendre votre réclamation.

Tsuyoshi Ito,

Je ne pense pas que ce soit correct. Par exemple, imaginez un réseau avec trois nœuds, la source s, le terminal t et un autre nœud v, avec trois arcs a1 = (s, v), a2 = (s, v), a3 = (v, t). Les capacités des arcs sont toutes de 1, et les temps de déplacement sont définis sur 0 pour a1 et a3, et 100 pour a2. Les durées de vie sont de 1 pour a1 et de 1000 pour a2 et a3. Ensuite, au temps 0, on peut envoyer une unité de flux à travers a1 et a3 de s à t, et commencer à envoyer une unité de flux à travers a2. Pendant les temps 1 à 99, a3 ne transporte aucun flux, car a1 a disparu, mais au temps 100, le flux à travers a2 arrive à v, et a3 est utilisé à nouveau.

Yoshio Okamoto,

Si je comprends bien, vous prétendez en partie qu'une fois que les heures de naissance / mort des bords sont fixées, le problème restant peut être résolu en utilisant l'approche classique du flux maximal dans le temps, mais je ne vois pas comment c'est le cas.

daveagp

@Yoshio: Dans ce cas, si, au lieu de commencer à envoyer une unité de flux le long de a2 immédiatement, vous avez cessé d'envoyer des flux, après un temps arbitrairement court, a1 pourrait être utilisé une fois de plus, et cela donnerait une meilleure solution.

Leandro M.

@Dave: non, ce n'est pas exactement ce que je prétends. Ce que je dis, c'est que chaque arc ne peut être utilisé qu'un nombre fini de fois, ou que les solutions au problème devraient approximativement arbitrer les solutions au débit maximal dans le temps. Je suis préoccupé par les détails de la définition du problème, en bref.

Leandro M.