Это было одной из наших идей, но показалось, что граф обычно либо не меняется вообще, либо меняется настолько сильно, что если сохранять положение вершин, то граф получится чересчур кривым. Например, в случае Декартова дерева, которое строится с нуля и должно иметь древовидную форму, сохранять положение вершин вообще не получится — они постоянно прыгают между поддеревьями. С другой стороны, отслеживать, что происходит с существующими вершинами, тоже сложно :)
Опубликуйте, пожалуйста, ответ на последний комментарий от dmagin:
Любопытно. Скажите, а эти веса вычисляются за экспоненциальное время? Где можно почитать про их вычисление?
Маловероятно, что NP-трудная задача решается за полиномиальное время. Это бы означало решение одной из важнейших нерешённых задач человечества: en.wikipedia.org/wiki/P_versus_NP_problem
Не исключено, что это может помочь. Подскажите, а как эти веса относятся к связности графа? Мы обсуждали, как найти небольшое множество вершин такое, что при его удалении граф распадётся на более-менее одинаковые по размеру компоненты связности.
Найти нужно точное минимальное вершинное покрытие. В правилах нет обязательного требования уметь доказывать своё решение, но вершинное покрытие не минимального размера на любом тесте ведёт к дисквалификации.
В соревновании есть трек по приближённым решениям для задачи нахождения древесной ширины (treewidth) графа. Для Vertex Cover засчитываются только точные решения.
Любопытная идея! Скажите, а как вы предлагаете искать сбаллансированные разрезы между парой вершин? Я использую потоковые алгоритмы в специальной сети и на первый взгляд выглядит так, будто они находят просто какой-то минимальный разрез, а не все. Более того, на самом деле, если углубиться в тонкости реализации, то кажется, что этот разрез будет смещён в сторону истока (т. е. одной из пары вершин, между которыми мы ищем разрез), хотя формализовать это утверждение у меня на первый взгляд не получается.
Про это тут также написано. Вершинные разрезы размером больше 1 в графах искать сложно, глобальный минимальный вершинный разрез в графе, кажется, ищется не лучше чем за кубическое время, а это слишком долго. Я пытался искать минимальный разрез между парами случайных вершин, но это не привело к улучшению результата.
На самом деле, проблема состоит в том, что нас интересуют не столько небольшие вершинные разрезы, сколько сбалансированные: нужно, чтобы граф распался на более-менее одинаковые по размеру компоненты связности. Какую бы метрику для этого я не пытался брать, у меня не получалось придумать полиномиального по времени подхода к такой задаче.
Так и происходит. Если граф после сокращения несвязный, задача на его компонентах связности решается независимо.
Единственное отличие от предложенной идеи — после этого этапа мы начинаем не с поиска мостов, а с поиска точек сочленения. Алгоритмы для поиска мостов и точек сочленения почти не отличаются друг от друга, но условие про точки сочленения чуть более сильное: заметим, что у нас после этапа сокращения не осталось вершин степени 1. Значит, если в нашем графе есть мост, то есть и точка сочленения. Обратное при этом неверно.
Любопытно. Скажите, а эти веса вычисляются за экспоненциальное время? Где можно почитать про их вычисление?
Маловероятно, что NP-трудная задача решается за полиномиальное время. Это бы означало решение одной из важнейших нерешённых задач человечества: en.wikipedia.org/wiki/P_versus_NP_problem
В соревновании есть трек по приближённым решениям для задачи нахождения древесной ширины (treewidth) графа. Для Vertex Cover засчитываются только точные решения.
На самом деле, проблема состоит в том, что нас интересуют не столько небольшие вершинные разрезы, сколько сбалансированные: нужно, чтобы граф распался на более-менее одинаковые по размеру компоненты связности. Какую бы метрику для этого я не пытался брать, у меня не получалось придумать полиномиального по времени подхода к такой задаче.
Единственное отличие от предложенной идеи — после этого этапа мы начинаем не с поиска мостов, а с поиска точек сочленения. Алгоритмы для поиска мостов и точек сочленения почти не отличаются друг от друга, но условие про точки сочленения чуть более сильное: заметим, что у нас после этапа сокращения не осталось вершин степени 1. Значит, если в нашем графе есть мост, то есть и точка сочленения. Обратное при этом неверно.