Увеличение способности максимизировать минимальное сокращение

9

Рассмотрим граф со всеми ребрами, имеющими единичную емкость. Можно найти минимальное сокращение за полиномиальное время.

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

user14373
источник
Я не уверен, что понимаю ваш вопрос: «Каков оптимальный способ выбора k таких ребер, чтобы максимизировать минимальное сокращение?», Вы имеете в виду минимальное сокращение 1) графика с унитарными мощностями или 2) графика с общими мощностями ?
Джереми

Ответы:

3

Теорема. Проблема в посте NP-сложная.

Под «проблемой в посте» я подразумеваю, учитывая граф и целое число , чтобы выбрать ребер, чтобы увеличить возможности, чтобы максимизировать минимальное сокращение в модифицированном графе.G=(V,E)kk

Идея состоит в том, чтобы уменьшить от Max Cut. Грубо говоря, данный граф имеет максимальный размер среза том и только в том случае, если вы можете увеличить пропускную способность ребер, чтобы получающийся граф имел минимальный размер среза . Идея состоит в том, что ребер достаточно, чтобы результирующий граф имел только один разрез конечной емкости, и это может быть любой разрез, который вы выберете.G=(V,E)sn2sn2

Эта идея не совсем работает, потому что для получения заданного среза вам нужно соединить подграфы, вызванные и каждый. Но вы можете обойти это с помощью соответствующего гаджета.(C,VC)CVC

Доказательство. Для заданного связного графа определите связный разрез, чтобы быть разрезом таким образом, чтобы каждый подграф, индуцированный и , был связан. Определите Max Connected Cut как проблему поиска связанного разреза (в данном связанном графе), максимизирующего количество ребер, пересекающих разрез.G=(V,E)(C,VC)CVC

Мы показываем, что Max Connected Cut сводится к проблеме в посте. Затем мы показываем, что невзвешенный Max Cut сводится к Max Connected Cut.

Лемма 1. Max Connected Cut сокращает время на поли до проблемы, определенной в посте.

Доказательство. Для данного экземпляра Max-Connected-Cut пусть . Чтобы доказать лемму, докажем следующее:G=(V,E)k=|V|2

Утверждение 1. Для любого в емкости есть связное сокращение по крайней мере, , если IFF можно увеличить краевых мощностей в до бесконечности, чтобы результирующий граф имел min сократить мощность как минимум .s>0(C,VC)GskGs

ТОЛЬКО ЕСЛИ: Предположим, что есть связанный срез по меньшей мере . Пусть и будут поддеревьями, охватывающими, соответственно, и , затем увеличим емкости ребер в и . (Обратите внимание, что .) Тогда в графе остается только ограничение конечной емкости , емкостью не менее , поэтому результирующий график имеет минимальную пропускную способность не менее .(C,VC)sT1T2CVCT1T2|T1|+|T2|=|C|1+|VC|1=|V|2=k(C,VC)ss

IF: Предположим, можно увеличить ребер в так, чтобы результирующий граф имел минимальную пропускную способность как минимум . Рассмотрим подграф, образованный рельефными ребрами. Без ограничения общности предположим, что этот подграф является ациклическим. (В противном случае «поднимите» одно ребро из цикла поднятых ребер и вместо этого поднимите не поднятое ребро, которое соединяет два соединенных компонента из подграфа. Это только увеличивает минимальное сечение в результирующем графе.) При выборе у подграфа выпуклых ребер есть два связанных компонента, скажем, и , поэтому единственный результирующий граф с конечной емкостью - этоkGskk=n2CVC(C,VC), И этот срез имеет емкость не менее , как это было в исходном графике.s

Это доказывает утверждение (и лемму). (КЭД)

Для полноты мы покажем, что Max Connected Cut является NP-завершенным путем сокращения от невзвешенного Max Cut.

Лемма 2. Невзвешенный Max Cut сокращает время поли до Max Connected Cut .

Доказательство. Для любого целого числа , определяют график состоит из двух путей и , каждый длиной , с ребрами из каждой вершины в к каждой вершине в . Мы оставляем читателю в качестве упражнения, чтобы убедиться, что максимальный разрез в ( с одной стороны, с другой) имеет размер , и ни один другой разрез не имеет размер больше, чем, скажем, .N1P(N)ABNABP(N)ABN2N2N/100

Вот сокращение. Для любого невзвешенного экземпляра Max Cut построим граф следующим образом. Пусть, Пусть . Добавьте к определенный выше граф (с двумя его путямиG=(V,E)G=(V,E)n=|V|N=100(n2+2n)GP(N)A а также B). Из каждой вершиныvV добавить ребро к одной вершине в A и другой край одной вершины в B, Это определяет сокращение. В завершение докажем, что это правильно:

Пункт 2: для любогоs0есть разрез (C,VC) в G по меньшей мере sМФЛ есть связанный разрез в G размером как минимум s+N2+n,

ТОЛЬКО ЕСЛИ: с учетом любого сокращения (C,VC) в G по меньшей мере sрассмотрим связанный срез (AC,BVC) в G, Это связано врезатьсяG режет по крайней мере s края от C в VCплюс N2 края от A в Bплюс n из 2n края от V в AB,

ЕСЛИ: Предположим, что есть связанный разрез в G размером как минимум s+N2+n, A а также Bнаходятся на противоположных сторонах разреза. (В противном случае, так как второй по величине сокращение вP(N) режет максимум N2N/100 края в P(N)общее количество обрезанных кромок не более N2N/100+|E|+2|V|N2N/100+n2+2n=N2.) Позволять C обозначить вершины в V на стороне разреза с A, Тогда естьN2 края в разрезе от A в B, а также n от V в ABтак должно быть хотя бы s от C в VC,

Это доказывает утверждение и лемму 2. (QED)

По леммам 1 и 2, поскольку невзвешенный Max Cut является NP-сложным, проблема в посте также NP-сложная.

Нил Янг
источник
Это также показывает, что проблема «увеличения k ребер для максимизации разреза» для заданного s а также t NP-полный (выбрать s а также t быть вершинами в A а также Bсоответственно).
Даниелло