Comments 22
А почему бы не проверить на связность?
Т.е. первым шагом просто исключаем неконфликтные вершины (вместе с ребрами), а потом проверяем, является ли оставшийся граф односвязным?
Если не является, значит он распадается на более простые подзадачи.
Если является односвязным, то есть ли в нем области слабой связности, соединенные друг с другом одним ребром? Если есть, то начать рассмотрение с вершин этих ребер.
Т.е. первым шагом просто исключаем неконфликтные вершины (вместе с ребрами), а потом проверяем, является ли оставшийся граф односвязным?
Если не является, значит он распадается на более простые подзадачи.
Если является односвязным, то есть ли в нем области слабой связности, соединенные друг с другом одним ребром? Если есть, то начать рассмотрение с вершин этих ребер.
Так и происходит. Если граф после сокращения несвязный, задача на его компонентах связности решается независимо.
Единственное отличие от предложенной идеи — после этого этапа мы начинаем не с поиска мостов, а с поиска точек сочленения. Алгоритмы для поиска мостов и точек сочленения почти не отличаются друг от друга, но условие про точки сочленения чуть более сильное: заметим, что у нас после этапа сокращения не осталось вершин степени 1. Значит, если в нашем графе есть мост, то есть и точка сочленения. Обратное при этом неверно.
Единственное отличие от предложенной идеи — после этого этапа мы начинаем не с поиска мостов, а с поиска точек сочленения. Алгоритмы для поиска мостов и точек сочленения почти не отличаются друг от друга, но условие про точки сочленения чуть более сильное: заметим, что у нас после этапа сокращения не осталось вершин степени 1. Значит, если в нашем графе есть мост, то есть и точка сочленения. Обратное при этом неверно.
А если граф не имеет точек сочленения, но при этом имеются N точек, удаление которых повышает связность?
Т.е. представьте две области, соединенные двумя или тремя точками, одновременное удаление которых разбивает граф на две области связности…
Т.е. представьте две области, соединенные двумя или тремя точками, одновременное удаление которых разбивает граф на две области связности…
Про это тут также написано. Вершинные разрезы размером больше 1 в графах искать сложно, глобальный минимальный вершинный разрез в графе, кажется, ищется не лучше чем за кубическое время, а это слишком долго. Я пытался искать минимальный разрез между парами случайных вершин, но это не привело к улучшению результата.
На самом деле, проблема состоит в том, что нас интересуют не столько небольшие вершинные разрезы, сколько сбалансированные: нужно, чтобы граф распался на более-менее одинаковые по размеру компоненты связности. Какую бы метрику для этого я не пытался брать, у меня не получалось придумать полиномиального по времени подхода к такой задаче.
На самом деле, проблема состоит в том, что нас интересуют не столько небольшие вершинные разрезы, сколько сбалансированные: нужно, чтобы граф распался на более-менее одинаковые по размеру компоненты связности. Какую бы метрику для этого я не пытался брать, у меня не получалось придумать полиномиального по времени подхода к такой задаче.
Задача для MaxSat.
Я пробовал несколько раз искать разрезы между парами случайных вершин и брать из них самый сбалансированный.
А что будет, если не случайные пары вершин брать, а псевдопериферийные?
Вот есть такое ощущение, что из-за «вытянутости» полученного графа на нем найдется несколько минимальных разрезов. И можно будет выбрать более-менее сбалансированный.
И не так даже…
1. Найти две псевдопериферийные точки (псевдодиаметр);
2. Исключить узел высокой степени примерно посредине между ними.
3. Если связность возросла, то к п. 6.
4. Уточнить псевдодиаметр.
5. Повторить с п. 2.
6. Повторить п.п. 2-5 для каждой компоненты связности, содержащей больше одного узла.
Но тут есть невнятный момент — метрика, учитывающая баланс между «примерно посредине» и «высокой степени». Можно поиграть крайними случаями — удалять узел наибольшей степени вне зависимости от положения, либо узел посредине, вне зависимости от степени (если несколько, то наибольшей степени из них). И посмотреть, что выйдет.
1. Найти две псевдопериферийные точки (псевдодиаметр);
2. Исключить узел высокой степени примерно посредине между ними.
3. Если связность возросла, то к п. 6.
4. Уточнить псевдодиаметр.
5. Повторить с п. 2.
6. Повторить п.п. 2-5 для каждой компоненты связности, содержащей больше одного узла.
Но тут есть невнятный момент — метрика, учитывающая баланс между «примерно посредине» и «высокой степени». Можно поиграть крайними случаями — удалять узел наибольшей степени вне зависимости от положения, либо узел посредине, вне зависимости от степени (если несколько, то наибольшей степени из них). И посмотреть, что выйдет.
Любопытная идея! Скажите, а как вы предлагаете искать сбаллансированные разрезы между парой вершин? Я использую потоковые алгоритмы в специальной сети и на первый взгляд выглядит так, будто они находят просто какой-то минимальный разрез, а не все. Более того, на самом деле, если углубиться в тонкости реализации, то кажется, что этот разрез будет смещён в сторону истока (т. е. одной из пары вершин, между которыми мы ищем разрез), хотя формализовать это утверждение у меня на первый взгляд не получается.
Любопытная, но, к сожалению, никуда не годная в текущем виде…
Дело в том, что растягивание графа вдоль псевдодиаметра даст нам «веретено» — степень самих крайних точек и близких к ним будет скорее всего ниже, чем точек между ними. А, следовательно, минимальный разрез будет отсекать как раз конечные точки, но не делить пополам.
Так что, нужна какая-то метрика, учитывающая как степень узла, так и его удаленность от «центра» псевдодиаметра.
Например такая: M = S*D1*D2, где S — степень узла, D1, D2 — расстояние до концов псевдодиаметра.
Находим точку с наибольшей такой метрикой и удаляем ее. Сначала это будет приводить к линеаризации графа, а потом он начнет рассыпаться на составляющие.
P.S. можно поиграть с метрикой M= (S^n) * D1 * D2, где n как-то зависит от числа узлов в графе.
И никаких поисков минимальных разрезов. Просто режем самые запутанные клубки в глубине.
Я вот чего не понял — надо найти точное решение или хорошее приближенное?
Дело в том, что растягивание графа вдоль псевдодиаметра даст нам «веретено» — степень самих крайних точек и близких к ним будет скорее всего ниже, чем точек между ними. А, следовательно, минимальный разрез будет отсекать как раз конечные точки, но не делить пополам.
Так что, нужна какая-то метрика, учитывающая как степень узла, так и его удаленность от «центра» псевдодиаметра.
Например такая: M = S*D1*D2, где S — степень узла, D1, D2 — расстояние до концов псевдодиаметра.
Находим точку с наибольшей такой метрикой и удаляем ее. Сначала это будет приводить к линеаризации графа, а потом он начнет рассыпаться на составляющие.
P.S. можно поиграть с метрикой M= (S^n) * D1 * D2, где n как-то зависит от числа узлов в графе.
И никаких поисков минимальных разрезов. Просто режем самые запутанные клубки в глубине.
Я вот чего не понял — надо найти точное решение или хорошее приближенное?
Найти нужно точное минимальное вершинное покрытие. В правилах нет обязательного требования уметь доказывать своё решение, но вершинное покрытие не минимального размера на любом тесте ведёт к дисквалификации.
В соревновании есть трек по приближённым решениям для задачи нахождения древесной ширины (treewidth) графа. Для Vertex Cover засчитываются только точные решения.
В соревновании есть трек по приближённым решениям для задачи нахождения древесной ширины (treewidth) графа. Для Vertex Cover засчитываются только точные решения.
Я не вникал в проблему «вершинного покрытия». Но срезонировал на термины «метрика» и «точки сочленения».
Поскольку связный граф обладает «резистивной метрикой», то в нем существует «ортоцентр». Данный центр определяется набором барицентрических координат (весов) вершин графа. Так вот,- точки сочленения графа имеют минимальные веса.
Возможно, это свойство как-то можно использовать в данной задаче.
Я, правда, не интересовался, как считаются данные (ортогональные) веса в графах из тысячи вершин. Возможно, тут сложность еще больше.
Поскольку связный граф обладает «резистивной метрикой», то в нем существует «ортоцентр». Данный центр определяется набором барицентрических координат (весов) вершин графа. Так вот,- точки сочленения графа имеют минимальные веса.
Возможно, это свойство как-то можно использовать в данной задаче.
Я, правда, не интересовался, как считаются данные (ортогональные) веса в графах из тысячи вершин. Возможно, тут сложность еще больше.
Не исключено, что это может помочь. Подскажите, а как эти веса относятся к связности графа? Мы обсуждали, как найти небольшое множество вершин такое, что при его удалении граф распадётся на более-менее одинаковые по размеру компоненты связности.
Да, немного посмотрел и похоже, что на основе данных весов как раз и решается задача вершинного покрытия. Как это доказать, пока не знаю, но на простых графах проверяется прямым вычислением.
Считаем координаты ортоцентра, сортируем компоненты по возрастанию, верхние k вершин и будут искомым решением.
Считаем координаты ортоцентра, сортируем компоненты по возрастанию, верхние k вершин и будут искомым решением.
Вот, чтоб понятнее было, — значения координат ортоцентра для графа из статьи:
Daniel -0.219
Bob -0.125
Fedor 0.031
Christos 0.125
Eric 0.344
Gerhard 0.344
Alice 0.500
Видим, что ключевые узлы тут — это Daniel, Bob и Fedor. Если удалять троих, то скорее всего надо удалять данные узлы. Но если удалять можно только двоих, то следует учитывать, что после какого-либо узла веса остальных меняются. После удаления Daniel ключевым узлом становится Fedor и надо удалять именно его (а не Bob):
Fedor -0.5
Bob 0
Christos 0
Alice 0.5
Gerhard 0.5
Eric 0.5
Daniel -0.219
Bob -0.125
Fedor 0.031
Christos 0.125
Eric 0.344
Gerhard 0.344
Alice 0.500
Видим, что ключевые узлы тут — это Daniel, Bob и Fedor. Если удалять троих, то скорее всего надо удалять данные узлы. Но если удалять можно только двоих, то следует учитывать, что после какого-либо узла веса остальных меняются. После удаления Daniel ключевым узлом становится Fedor и надо удалять именно его (а не Bob):
Fedor -0.5
Bob 0
Christos 0
Alice 0.5
Gerhard 0.5
Eric 0.5
Опубликуйте, пожалуйста, ответ на последний комментарий от dmagin:
Любопытно. Скажите, а эти веса вычисляются за экспоненциальное время? Где можно почитать про их вычисление?
Маловероятно, что NP-трудная задача решается за полиномиальное время. Это бы означало решение одной из важнейших нерешённых задач человечества: en.wikipedia.org/wiki/P_versus_NP_problem
Любопытно. Скажите, а эти веса вычисляются за экспоненциальное время? Где можно почитать про их вычисление?
Маловероятно, что NP-трудная задача решается за полиномиальное время. Это бы означало решение одной из важнейших нерешённых задач человечества: en.wikipedia.org/wiki/P_versus_NP_problem
Прямой расчет координат ортоцентра сводится к обращению лапласиана графа. Надо получить грамиан (можно через матрицу резистивных расстояний), окаймить его единицами (как матрицу Кэли-Менгера) и снова обратить. То есть сложность тут совпадает со сложностью обращения матриц. Но скорее всего должны быть и другие, менее затратные способы.
Я для хабра написал целую серию про подобие пространств симплексов и графов. Получилось не особо, но примерное представление о том, откуда в графах берется ортоцентр, надеюсь, дает. В первой статье, оказывается, я даже указал на связь весов ортоцентра и узлов сочленения графа.
Для простых типов графов существуют конечные формулы расчета компонент ортоцентра (деревья, цепочки, колеса, фаны).
Я для хабра написал целую серию про подобие пространств симплексов и графов. Получилось не особо, но примерное представление о том, откуда в графах берется ортоцентр, надеюсь, дает. В первой статье, оказывается, я даже указал на связь весов ортоцентра и узлов сочленения графа.
Для простых типов графов существуют конечные формулы расчета компонент ортоцентра (деревья, цепочки, колеса, фаны).
Матрицы обращаются за кубическое время. Маловероятно, что задача о вершинном покрытии решается за кубическое время, это было бы большим прорывом.
Нужен контрпример, в котором узлы вершинного покрытия не совпадут с минимальными компонентами ортоцентра.
Насчет вероятности «большого прорыва». Индекс Кирхгофа, например, тоже можно считать перебором всех возможных деревьев графа. А можно тупо определитель минора лапласиана посчитать и не париться ).
Компоненты ортоцентра очевидно связаны с комбинаторикой графа (и индексом Кирхгофа). Но надо чуть глубже тут копнуть.
Насчет вероятности «большого прорыва». Индекс Кирхгофа, например, тоже можно считать перебором всех возможных деревьев графа. А можно тупо определитель минора лапласиана посчитать и не париться ).
Компоненты ортоцентра очевидно связаны с комбинаторикой графа (и индексом Кирхгофа). Но надо чуть глубже тут копнуть.
Ну в общем-то и копать глубоко не пришлось. Значения компонент ортоцентра, умноженные на индекс Кирхгофа, отражают сумму компонент всех остовных деревьев, на которые раскладывается данный граф. В свою очередь компоненты деревьев считаются просто: c(i) = 1 — v(i). Здесь v(i) — степень (валентность) i-го узла.
В итоге получаем, что отрицательное значение компоненты какого-либо узла исходного графа означает, что данный узел чаще является точкой сочленения в остовах графа. То есть значения компонент ортоцентра — это статистика валентности по всем возможным конфигурациям деревьев на данном графе.
В итоге получаем, что отрицательное значение компоненты какого-либо узла исходного графа означает, что данный узел чаще является точкой сочленения в остовах графа. То есть значения компонент ортоцентра — это статистика валентности по всем возможным конфигурациям деревьев на данном графе.
Тут пошли уже такие зауми (индексы Кирхгофа, лапласианы, матрицы Кэли-Мэнгера), что я почувствовал себя чужим на этом празднике жизни :)
А скажите мне,благородные доны, чей это вертолет позади избы задача о минимальном вершинном покрытии и задача о максимальном независимом множестве полностью эквивалентны или нет?
А скажите мне,
Дополнением наименьшего вершинного покрытия в графе является наибольшее независимое множество. Если речь о точном решении, то это эквивалентные задачи(в общем короткий и наивный ответ да.), если о приближенном то нет. Также вопросы есть ли вершинное покрытие размера k и есть ли независимое множество размера k скорее всего вопросы различной сложности. Так первое решается за 2^k poly(n), а про второе считается что скорее всего нет.
Sign up to leave a comment.
Как решать NP-трудные задачи с помощью параметризованных алгоритмов