Обрезка сильно связанного орграфа

10

Учитывая сильно связанный орграф G со взвешенными ребрами, я хотел бы идентифицировать ребра, которые доказуемо не являются частью какого-либо минимального сильно связного подграфа (MSCS) группы G.

Одним из способов нахождения таких ребер является модифицированный алгоритм Флойда-Варшалла. Используя алгоритм Флойда-Варшалла, можно определить, какие ребра никогда не являются наилучшим вариантом для перехода от вершины i к j. Эти узлы не могут быть частью MSCS, потому что лучше заменить их двумя или более другими ребрами.

Техника обрезки Флойд-Варшалла работает довольно хорошо, когда граничные веса значительно различаются, но очень плохо, когда граничные веса одинаковы, но велики по величине.

Знаете ли вы какие-либо эффективные методы обрезки для больших, схожих краев? Эта проблема эквивалентна более распространенной проблеме, которую я не узнаю? Этот вид обрезки изучался ранее в литературе?

Nate
источник
1
Я не могу ответить на этот вопрос, не читая литературу по проблеме. Вы сами пытались читать литературу? Можете ли вы обобщить то, что вы нашли?
Уоррен Шуди
1
Большая часть литературы посвящена поиску алгоритмов аппроксимации, некоторые из которых довольно хороши. Большинство из них работают за счет сокращения цикла с хорошими результатами. У меня возникают проблемы с поиском литературы для обрезки вместо приближения, поэтому мне интересно, является ли проблема обрезки обобщением более распространенной проблемы, о которой я могу прочитать. Любые советы о том, что литература связана, будет приветствоваться.
Nate
1
Какую функцию аппроксимируют алгоритмы аппроксимации и чем она отличается от обрезки?
Суреш Венкат
Аппроксимации аппроксимируют минимальный сильно связный подграф. Как я уже сказал, они часто используют сокращение цикла, чтобы сделать это. Сокращение посредством сокращения цикла может привести к неоптимальному подграфу (следовательно, приближение). Я хочу сократить так, чтобы я мог гарантировать, что я не сокращал любые края, которые появляются MSCS.
Nate

Ответы:

3

Мы предполагаем, что веса ребер являются положительными целыми числами. Учитывая , ориентированный граф G с весами ребер, вызовите ребро е излишний , если адрес не принадлежит к какому - либо минимальному весу сильно связному остовному подграфы G .

Мы утверждаем, что, если P = NP, не существует алгоритма полиномиального времени, который всегда находит избыточное ребро в данном ориентированном графе с весами ребер, пока он есть. Точнее:

Теорема . Для ориентированного графа G с весами ребер сложно найти избыточное ребро в G или объявить, что у G нет лишнего ребра.

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

Лемма . Для заданного ориентированного графа G с весами ребер трудно вычислить вес сильно связанного остовного подграфа минимального веса в G даже при условии, что G имеет единственный остовный сильно связный подграф минимального веса.

Доказательство . Как вы знаете , проблема без обещания является NP-трудной (даже для случая единичного веса) из-за сокращения от проблемы гамильтоновой схемы. Мы сводим проблему без обещания к проблеме с обещанием.

Пусть G - ориентированный граф с весами ребер. Добавьте ребра G с помощью й 0 , х 1 , ..., х м -1 , где т есть число ребер в G . Пусть w i будет заданным весом ребра e i . Пусть новый вес wi = 2 m w i +2 i . Тогда легко проверить, что G с новыми весами имеет единственный сильно связный остовной подграф минимального веса. Также легко проверить, что минимальный весW сильно связного остовного подграфа в G с исходными весами можно вычислить из минимального веса W ′ в G с новыми весами как W = ⌊ W ′ / 2 m ⌋. КЕД .

Цуёси Ито
источник
2
Да, очевидно, в NP сложно найти все такие ребра. Я не ищу все такие ребра, я ищу набор ребер, которые можно определить как обрезанные за полиномиальное время. Алгоритм Флойда-Варшалла можно использовать для нахождения одного такого набора ребер, как описано выше. Мне было интересно, есть ли другие способы идентифицировать подмножество съемных ребер за полиномиальное время.
Nate