Супер Марио течет в НП?

Одним из классических расширений проблемы максимального потока является проблема «максимального потока во времени»: вам дается орграф, два узла которого различаются как источник и приемник, где каждая дуга имеет два параметра, - единичное время и задержка. Вы также дали горизонт времени . Цель состоит в том, чтобы вычислить поток с течением времени , который получает максимальное количество материала от источника к стоку по времени . Поток максимального значения может быть вычислен за полиномиальное время с помощью умного классического сокращения до минимального максимального расхода.$T$$T$

Меня интересует расширение этой модели, где у ребер есть третий параметр «продолжительности жизни». Если дуга имеет срок службы , а - самое раннее время, когда положительный поток посылается через дугу, то мы разрушаем дугу в момент времени . Вы можете думать об этом, как о платформах в Super Mario Brothers, которые падают / разрушаются вскоре после того, как вы наступили на них, или вы можете думать о них как о батареях, необходимых для питания краев, которые нельзя отключить после их включения. , ( Изменить :) Проблема решения заключается в том, что, когда также задана нижняя граница значения потока , можно ли запланировать поток, отвечающий как верхней границе временного горизонта, так и нижней границе значения потока.т т + ℓ $\ell$$t$$t+\ell$$B$

До сих пор я вижу, что эта проблема сильно NP-сложна (через 3 раздела). Но на самом деле я не знаю, есть ли это в NP: есть ли гарантия способа выразить решение компактно? В классическом варианте для обхода этой проблемы используется специальный тип оптимального потока.

Примечание: приведенная выше модель немного не указана, так как вы можете разрешить или запретить накопление потока в узлах, и у вас может быть модель с дискретным временем или непрерывная модель. Решение вопроса для любой из этих моделей было бы превосходным.

Прошло много времени, но я уверен, что эта проблема в P.

Я написал свою диссертацию на эту тему в 1995 году. См. «Алгоритмы эффективного динамического потока в сети» Брюса Хоппе, представленные в отделе Cornell CS. Онлайн на http://dspace.library.cornell.edu/bitstream/1813/7181/1/95-1524.pdf

См. Главу 8 «Расширения» раздел 8.1 о «смертных краях»

РЕДАКТИРОВАТЬ: ответ НЕПРАВИЛЬНО. Я сделал (глупое) неявное предположение, что, когда поток пути начинается в момент времени s и заканчивается в момент времени t и проходит через край e, он блокирует край e на это время. Однако это не так. Видеть *.

Примечание: возможно, этот подход излишне сложен или некорректен. Хотя я пытался проверить и записать это внимательно - я не тратил на это огромное количество времени.

Предполагается, что «накопление» не допускается, например, поток должен быть передан немедленно. Обозначим через количество ребер, а N - длину входа. Я не указывал непрерывное или дискретное время, поскольку не принимал его во внимание. Это должно работать для дискретного мышления, для непрерывного я уверен.$m$$N$

Затем мы можем описать решение как набор «путей-потоков» от источника к стоку. Путь потока - это четверка которая состоит из следующего: простой путь P от источника к стоку; Время начала пути потока s ; Объем потока через путь а ; Пропускная способность р .$(P,s,a,r)$$P$$s$$a$$r$

Пусть решение задано множеством -потоков. Мы можем проверить, является ли решение, данное этими путями, правильным во времени полиномом от | F | и N :$F$$|F|$$N$

• Для каждого фронта и момента времени t сложите пропускную способность всех потоков пути, проходящих через e в момент времени t . Каждый поток пути имеет время начала и окончания, поэтому нам нужно учитывать только моменты времени, когда поток пути начинается или заканчивается (между этими моментами ничего не меняется в отношении потоков пути, которые проходят через край e .$e$$t$$e$$t$$e$
• Для каждого пути-поток , мы можем проверить , поступает ли все это поток в раковине до того времени .$T$
• Для каждого ребра мы можем проверить, проходит ли поток пути после его уничтожения или нет.
• Нижнюю границу потока мы можем просто проверить, сложив суммы потоков путей потока.$B$

Теперь мы «просто» нужно показать , что число путь-потоков является многочленом .$N$

Для данного решения мы можем определить время, когда некоторый поток прошел границу и когда грань была разрушена. Преобразуйте это в проблему с эквивалентным решением: на каждом ребре есть жесткие границы, когда его можно использовать, а когда нет - время начала и окончания. Пусть обозначает множество всех этих времен.$\{t_1,...,t_k\}$

Рассмотрим некоторое некомпактное решение и (изначально) пустое множество путей. Идея состоит в том, что мы итеративно находим поток пути в некомпактном решении, удаляем его и сохраняем в нашем наборе потоков пути.

$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$

$[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$

Как я понимаю, вам нужно хранить только одно число на дугу, представляющее момент, когда поток начинает передаваться по дуге. Это предполагает, что после этого дуга становится непригодной для использования. Если, в противном случае, дуга может быть использована снова после того, как она перестанет использоваться, у нее должны быть решения, максимально приближенные к решениям с максимальным расходом с течением времени (поскольку поток может прекратить посылаться на сколь угодно малое количество времени, а затем начать перекачиваться снова ).