Покрытие множества множествами мощности 3

[stiv1995]

Добрый день,

в процессе решения более общей задачи возникла следующая:

пусть есть множество $S$ специальной формы: $S = \left\{1,1,2,2 \ldots, n,n | a_1, \ldots, a_n \right\}, \ |S| = 3n$. Есть также набор множеств мощности 3 вида $R_i = \left\{i, j | a_k \right\}, i \ne j$. Небходимо определить, есть ли среди семейства $R$ такая совокупность множеств $\left\{R_t \right\}_{t=1}^{n}$, что $\cup\limits_{t = 1}^n R_i = S$.

Иными словами, множество $S$ состоит из двух подгрупп, в первой находятся все натуральные числа от $1$ до $n$, каждое в двух экземплярах, во второй $n$ произвольных различных объектов. Каждое из множеств $R_i$ содержит пару различных элементов из первой группы и один объект во второй. Нужно выяснить, можно ли из $R_i$ выделить семейство, объединение которого в точности равно $S$.

Эта задача похожа на Exact Cover by 3-Set, но является менее общей. Поэтому возможно для нее существует алгоритм.

Спасибо!

[mihaild]

В множестве не может быть двух одинаковых элементов. У вас тут может мультимножество? Или что-то более сложное? $1,2$ и $2,1$ в $R$ - это одно и то же или нет?
Если просто мультимножество, то $a_i$ ни на что не влияют и их можно рассматривать отдельно. И дальше все просто (попробуйте для $n=2,3$ явно выписать, дальше должно быть понятно как аналогично делать).

[stiv1995]

Да, это мультимножество. $1,2$ и $2,1$ в $R$ это одно и то же. Я не очень понял, что значит $a_i$ можно рассматривать отдельно?

Привожу пример для $n = 2$:

$S = \left\{1, 1, 2, 2, a_1, a_2 \right\}$

В этом случае $R = \left\{ \left\{1,2,a_1 \right\}, \left\{1, 2, a_2 \right\} \right\}$ покрывает множество $S$.

здесь сложность в том, что объединение рассматривается тоже как объединение мультимножеств. Например, если $n = 3$

$S = \left\{1, 1, 2, 2, 3,3, a_1, a_2, a_3 \right\}$

В этом случае из семейства $R = \left\{ \left\{1,2,a_1 \right\}, \left\{1, 2, a_2 \right\}, \left\{1, 3, a_3 \right\} , \left\{2, 3, a_3 \right\} \right\}$ нелься выделить совокупность, покрывающую $S$.

А из семейства $R = \left\{ \left\{1,2,a_1 \right\}, \left\{2, 3, a_2 \right\}, \left\{1, 3, a_3 \right\} \right\}$ можно.

Легко придумать динамический алгоритм для решения задачи, но его сложность будет $O(2^n)$.

Вполне возможно, что эта задача и не имеет полиномиального алгоритма если $P \ne NP$, но это показать тоже пока не получилось.

[mihaild]

Пардон, невнимательно прочитал условие.
Ваша задача кажется делается так: строим транспортную сеть, из истока в каждую $a_i$ пускаем ребра пропускной способности $1$, добавляем слой $(I, j)$, в вершины которого идут ребра мощности $1$, соответствующие элементам $R$, дальше вершины, соответствующие отдельным числам и в конце сток.

[stiv1995]

Да вот проблема как раз в том, что с помощью максимального потока не получается решить задачу:
для вашей конструкции:
если вершина $(i, j)$ получает единицу потока она должна дать понять об этом обеим вершинам $i$ и $j$ в следующем слое, но у нее всего одна единица, так что не получается.

если изначально добавлять ребра пропускной способности $2$, то никак не получается гарантировать, что между первым и вторым слоем все ребра будут нести либо поток 2 либо 0. (Может получиться так, что некоторые ребра будут нести поток 1 и это никак не интерпретируемо). Я пытался как-то обойти это обстоятельство, но не удалось пока.

[mihaild]

Да, про разделение потока я не сообразил. Вроде получается что exact cover by 3-sets к этому сводится, но аккуратно расписать возможности пока нет.
Идея следующая: для каждого множества $x,y,z$ добавляем числа (для каждого множества свои) $v, 1, 2, 3$ и $a_i$, которые я буду для удобства обозначать просто латинскими буквами из начала алфавита. Плюс все исходное множество считаем пронумерованным.
Добавляем в $R$ группу 1 - элементы $(v,x|a), (x,y|b), (y,z|c), (z,v|d)$ - их будем брать, если наше множество входит в покрытие. Дополнительно добавляем группу 2 - $(1,2|a), (v,1|b), (3,v|c), (2,3|d)$ - их будем брать, если наше множество не входит в покрытие.
Чтобы все же покрыть 1,2,3, если наше множество входит в покрытие, добавляем ещё элементы $(1,2|e), (2,3|f), (3,1|g)$. Ну и чтобы захватить $e,f,g$, если множество не входит в покрытие, заранее добавляем отдельно столько чисел, сколько множество не попадет в покрытие, и соединяем $f,g,h$ со всеми возможными парами этих дополнительных чисел.
Если я ничего не путаю, то мы обязаны взять либо все элементы из группы один, либо все элементы из группы два. И по этому однозначно восстанавливается покрытие - в него входят все множества, для которых выбрана группа 1. Наоборот, по любому покрытию определяется, какую группу для каждого множества надо брать (а для $e,f,g$ из множеств, не взятых в покрытие, набрать что угодно из дополнительных чисел - например, сделать цикл).

[stiv1995]

ОК, спасибо большое. Идея построить сведение Exact Cover by 3 Set к этой задаче мне не приходила. Пока не очень понял Вашу конструкцию, но кажется что свести и впрямь можно. В любом случае я уже переключился на поиск аппроксимаций для этой задачи и вроде бы получается используя жадный алгоритм достичь удовлетворительной точности.

Еще раз спасибо за ответы!