Подграф с минимальным весом ребра и весом узла ›= Val

Я столкнулся с этой проблемой - в неориентированном графе каждый узел и ребро имеют вес. Все веса неотрицательны. Для заданного значения S найдите связный подграф с минимальной суммой весов ребер, такой, что его сумма весов узлов не меньше S.

Наиболее очевидное решение - это метод грубой силы с учетом всех возможных подграфов. Но временная сложность экспоненциальна. Есть ли лучший алгоритм для этого? Моя интуиция такова, что мы можем преобразовать веса узлов в веса ребер, а затем применить алгоритм связующего дерева. Но я не мог решить ее однозначно. Как решить эту проблему?

РЕДАКТИРОВАТЬ: Похоже, я недостаточно ясно понял описание подграфа. Выбранный подграф должен быть одним связным компонентом. Надеюсь, теперь все ясно.


graph algorithm time-complexity graph-algorithm
person Sashank    schedule 21.11.2015    source источник
comment
Ограничены ли веса вообще (например, все неотрицательные)? Если все веса неотрицательны, проблема становится тривиальной - возможно, вы хотите ограничить подграфы только теми подграфами, которые индуцированы набором ребер?   -  person Daniel Wagner    schedule 21.11.2015
comment
Все веса неотрицательны, и все ребра можно рассматривать. Как решить проблему?   -  person Sashank    schedule 21.11.2015
comment
С этими ограничениями решение тривиально: выбрать все узлы и ни одно из ребер. Вес ребра 0, вес узла определенно больше S, если это невозможно.   -  person Daniel Wagner    schedule 21.11.2015
comment
Извините, если вопрос не ясен. Все выбранные узлы необходимо соединить ребрами.   -  person Sashank    schedule 21.11.2015
comment
Правильно, поэтому мое предложение (только подграфы, вызванные набором ребер) появилось точно; или все выбранные узлы должны быть связаны, что означает что-то более сильное, например, только сильно связные подграфы?   -  person Daniel Wagner    schedule 21.11.2015
comment
Похоже, я многого не понимал. Это неориентированный граф. Да, нам нужно рассматривать подграфы, индуцированные набором ребер.   -  person Sashank    schedule 21.11.2015
comment
До сих пор неясно, должно ли решение быть связным (т. Е. Существует путь от каждой вершины к каждой другой вершине), или просто каждая вершина инцидентна некоторому край (это позволит разделить подключенные компоненты).   -  person j_random_hacker    schedule 21.11.2015
comment
Проверьте правку. Надеюсь, теперь все ясно.   -  person Sashank    schedule 21.11.2015
comment
Вы уверены, что имели в виду сильносвязный компонент вместо сильно связного подграфа? Сильносвязная компонента максимальна, и существуют эффективные алгоритмы ее нахождения.   -  person Daniel Wagner    schedule 21.11.2015
comment
Если бы вы могли решить эту проблему эффективно, не могли бы вы также решить en.wikipedia.org/wiki/Clique_problem качественно?   -  person mcdowella    schedule 21.11.2015
comment
Как заметил Даниэль Вагнер, «сильная связь» имеет особое значение - и, по сути, это термин, который может применяться только к направленным графам. Я также на 99% уверен, что вы просто имеете в виду подключено - и в этом случае сокращение templatetypedef является правильным, что означает, что это NP-сложно.   -  person j_random_hacker    schedule 25.11.2015
comment
Я не знал, что сильно связный используется только для ориентированных графов. Я имел ввиду только подключенный. Есть ли методы динамического программирования для решения этой проблемы?   -  person Sashank    schedule 25.11.2015

Ответы (1)


arrow_upward
3
arrow_downward

Я думаю, что эта проблема является NP-сложной из-за редукции проблемы дерева Штейнера. Для графа G и набора узлов S, которые необходимо покрыть, установите вес всех узлов в S равным одному, а всем остальным узлам равным 0. Подграф с весом узла не менее | S | с минимальной общей стоимостью ребра должно быть деревом (если есть какие-либо циклы, удаление ребра из цикла только снижает стоимость) и должно соединять все узлы, которые необходимо охватить. Следовательно, это дерево Штейнера. В целом, это сокращение может быть вычислено за полиномиальное время, поэтому ваша проблема NP-сложная.

person templatetypedef    schedule 21.11.2015
comment
Из обновления кажется, что решения не нужно связывать - поэтому решением этой проблемы может быть лес, а не связующее дерево, следовательно, не решение проблемы Штайнера. - person Daniel Wagner; 21.11.2015
comment
@DanielWagner По-прежнему возникает вопрос о связном подграфе - возможно, я что-то упускаю? - person templatetypedef; 21.11.2015
comment
Да, вы правы - с тех пор, как я написал свой комментарий, были дальнейшие разъяснения. Извинения! - person Daniel Wagner; 21.11.2015
comment
@templatetypedef Есть ли способы динамического программирования для решения этой проблемы? - person Sashank; 25.11.2015
comment
@Sashank Не знаю, но есть хорошие алгоритмы приближения для дерева Штейнера на случай, если это поможет. - person templatetypedef; 25.11.2015