Количество вершин, присутствующих во всех максимальных совпадениях

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

Есть ли решение помимо очевидного удаления каждой вершины и найти максимальное совпадение, чтобы увидеть, как оно уменьшается?

graph-theory graph-algorithms Хоууин Кёма
источник

Я не понимаю, как то, что вы предложили, является даже решением.

$\:$ (Рассмотрим треугольник.)

$\hspace{1.4 in}$

@RickyDemer сначала мы находим максимальное соответствие во всем графике. Затем мы удаляем вершину и снова находим максимальное совпадение. Если разница равна 1, то мы можем сказать, что эта вершина присутствует во всех максимальных совпадениях.

evil999man

Следует ли заменить «найти максимальное соответствие» на «найти максимальное соответствие» или «найти все максимальные соответствия»?

$\;$

Я думаю, что это должно быть заменено размером максимального соответствия.

evil999man

@ Отлично, верно. Я отредактирую свой вопрос.

Хоууин Кёма

Ответы:

$O(n^3)$

Томас Калиновский
источник

Мне нужны только размеры, а не сами вершины. Можно ли это сделать в O (n ^ 2)? И спасибо за статью

Хоууин Кёма

$v$

Выполнив два поиска в ширину или вглубь: один, чтобы найти части графа, которые могут быть достигнуты из несопоставленных вершин, и один, чтобы найти части, которые могут достичь несопоставленных вершин, вы можете найти необходимые вершины в линейном времени, как только вы уже есть соответствие.

Возможно, что-то подобное будет работать и для случая, не связанного с двусторонним участием, с использованием поиска альтернативного пути с сокращением цветов, но детали будут более сложными.

Дэвид Эппштейн
источник

Мне интересно, как бы вы сделали это в общем графике. Не могли бы вы объяснить это?

evil999man

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

Дэвид Эппштейн

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

Хоууин Кёма