Нахождение максимального соотношения min cut в остовном дереве графа

Question

Я думаю о проблеме в графах, одна часть этой проблемы выглядит так:

У нас есть граф G = (V, E) и его остовное дерево T = (V, F) (F - это подмножество E), для каждого минимального разреза в G (на E), который разбивает график на два подграфа с узлами (U, U ') (необязательно для каждого подключаемого подграфа), мы проверяем размерэто сокращение в F, назовите размер их G (U, U ') и T (U, U'), я хочу найти:

ratio = max{T(U,U')/G(U,U')} for all possible U,U'

Я думаю, что это NP-Hard, но я не могуДокажите это.Здесь что-то очевидно, то есть если у нас есть вершина в T с такой же степенью, что и у G, коэффициент равен 1, также очевидно, что 0

U пересекаются с U '= нулемU union U '= V, и ни один из U и U' не пуст.

Answer 1

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