«(1: k) сопоставление деревьев» - разрешимо за полиномиальное время?

Question

Несколько месяцев назад был хороший вопрос относительно " 1: n сопоставления проблемы ", и, похоже, не существует алгоритма поли-времени.

Я хотел бы добавить ограничения, чтобы найти максимальное совпадение для задачи согласования 1: n с полиномиальным алгоритмом. Я хотел бы сказать: «Для вершины A1 выберите либо {B1, B2, B5}, либо {B2, B3}, если вершины еще не взяты из другой A-вершины», т. Е. Я бы не допустил все возможные комбинации.

Это можно выразить, если мы введем вспомогательные вершины H для каждого выбора и заменим ребра деревьями =>, и мы получим задачу, аналогичную обычному двустороннему сопоставлению. Каждая вершина A или B может иметь только одно ребро в сопоставлении. Ребра в или из вершин в H либо все в сопоставлении, либо ни один из них не присутствует в сопоставлении. Представьте себе следующий трехсторонний граф:

Теперь определите h_ij = "корень дерева, который содержит H_ij", чтобы легко выразить соответствие:

• Тогда в примере M = {h12, h22} будет одно «максимальное» совпадение, хотя задействованы не все вершины из B
• Набор {h12, h23} не совпадает, потому что тогда B3 должен был бы быть выбран дважды.

Будет ли эта проблема разрешима за полиномиальное время? Если да, то есть ли временное решение для взвешенного (w (h_ij)) варианта? Если нет, не могли бы вы спорить или даже доказать это для такого «простого человека», как я, или предложить другие ограничения для решения проблемы соответствия 1: n?

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

PS: не домашняя работа ;-)

Answer 1

Существует разница между максимальным и максимальным . Я предположил, что вы имели в виду максимум для приведенной ниже записи.

Вы, похоже, не очень четко определили свою проблему, но если я правильно понял ваше намерение, похоже, что ваша проблема выполнена NP полностью (и "эквивалентна" Установить упаковку ).

Мы можем предположить, что разрешенные размеры наборов одинаковы (k) для всех A_i, чтобы найти соответствие [1: k], так как любой другой размер набора можно игнорировать. Чтобы найти max k, мы просто запускаем алгоритм для [1: k] для k = 1,2,3 .. и т. Д.

Итак, ваша проблема (я думаю ...):

Учитывая m наборов семейств F_i = {S_1i, .., S_n(i)i} (| F_i | = размер F_i = n (i), не обязательно должен быть таким же, как | F_j |), каждый набор размера k вы должны найти один набор из каждого семейства ( скажем S_i) такой, что

• S_i и S_j не пересекаются для любого i neq j.
• максимальное количество S_i.

Мы можем показать, что NP-Complete для k = 3, в два этапа:

1. Задача NP-Complete Набор Упаковки можно уменьшить. Это показывает, что это NP-Hard.
2. Ваша проблема в NP и может быть уменьшена до Set Packing. Это и 1) подразумевает, что ваша проблема - NP-Complete. Это также поможет вам использовать любые алгоритмы аппроксимации / рандомизации, уже существующие для Set-Packing.

Набор Упаковка является проблемой:

Для n наборов S_1, S_2, ..., S_n найдите максимальное количество попарно непересекающихся наборов среди них.

Эта проблема остается NP-полной, даже если | S_1 | = | S_2 | = ... = | S_n | = 3 и называется задачей упаковки с 3 наборами.

Мы будем использовать это, чтобы показать, что ваша проблема связана с NP-Hard, обеспечивая простое сокращение от упаковки из 3 комплектов до вашей проблемы.

Учитывая S_1, S_2, .., S_n просто образуют семейства

F_i = {S_i}.

Теперь, если у вашей задачи было решение за полиномиальное время, мы получаем набор множеств {S_1, S_2, ..., S_r}, таких что

• S_i и S_j не пересекаются
• Максимальное количество S_i.

Это простое сокращение дает нам решение проблемы упаковки из 3-х комплектов, поэтому ваша проблема - NP-Hard.

Чтобы увидеть, что эта проблема в NP, мы уменьшаем ее до Set-Packing следующим образом:

Дано F_i = {S_1i, S_2i, ..., S_ni}

мы рассматриваем наборы T_ji = S_ji U {i} (т.е. мы добавляем id семейства в сам набор) и запускаем их через алгоритм Set-Packing. Я оставлю это вам, чтобы понять, почему решение Set-Packing дает решение вашей проблемы.

---

Для решения maximal все, что вам нужно, - это жадный алгоритм. Просто продолжайте собирать наборы, пока не сможете выбрать больше. Это будет полиномиальное время.