Задача о покрытии множествами

Пусть дано конечное множество \(U\) из \(n\) элементов, набор его подмножеств \(\mathcal{S}=\left\{ S_{1}, \ldots , S_{k}\right\} \subset 2^U\). В частности, если \(\left|S_i\right| = 2, \; \forall i\), то \((U, \mathcal{S})\) – это неориентированный граф. Поднабор \(\mathcal{S}^{\prime } \subseteq \mathcal{S}\) называется покрытием, если любой элемент из \(U\) принадлежит хотя бы одному элементу из \(\mathcal{S}^{\prime }\). Т.е.

\[ \bigcup _{S \in \mathcal{S}'}S = U \]

Задача о покрытии множествами минимальной мощности

Конечное множество \(U\) из \(n\) элементов, набор его подмножеств \(\mathcal{S} \subset 2^U\).

Минимальное по мощности покрытие из \(\mathcal{S}\).

Задача о покрытии множествами минимальной мощности

Универсум \(U\) из 9 элементов и семейство \(\mathcal S=\{S_1,\dots,S_6\}\) перекрывающихся подмножеств. Наведите курсор на подпись множества, чтобы выделить его и увидеть элементы; на точку — чтобы узнать, в какие множества она входит.

Обобщение данной задачи – задача о покрытии множествами минимального веса. Мы будем ее рассматривать.

Задача о покрытии множествами минимального веса

Конечное множество \(U\) из \(n\) элементов, набор его подмножеств \(\mathcal{S} \subset 2^U\) и веса подмножеств \(c: \mathcal{S} \rightarrow \mathbf{Q}^{+}\).

Минимальный по весу поднабор из \(\mathcal{S}\), покрывающий множество \(U\).

Задача о покрытии множествами минимального веса

Та же конфигурация \(U,\mathcal S\), но каждому множеству \(S_i\) приписан вес \(c(S_i)\) (число под подписью). Наведите курсор на подпись множества, чтобы выделить его.

1 Жадный алгоритм для задачи о покрытии множествами

В 1979 году чешский математик Вацлав Хватал предложил жадный алгоритм для задачи о покрытии множествами.

Algorithm 1 Жадный алгоритм Хватала для задачи о покрытии множествами (\(U, S, c: S \rightarrow Q^{+}\))

• \(C \gets \varnothing\) (Множество уже покрытых элементов из \(U\))
• \(\operatorname{Sol} \gets \varnothing\) (Множество выбранных подмножеств из \(S\))
• пока \(C \neq U\) выполнять
  • Выбрать множество \(S_{i} \in S \setminus \operatorname{Sol}\), минимизирующее \[ \alpha_{i} = \frac{c(S_i)}{|S_i \setminus C|} \] (стоимость за единицу ещё непокрытого элемента)
  • для каждого \(u \in S_i \setminus C\) выполнять
    • \(\operatorname{price}(u) \gets \frac{c(S_i)}{|S_i \setminus C|}\) (назначаем цену каждому новому покрытому элементу)
  • \(C \gets C \cup S_i\) (обновляем множество покрытых элементов)
  • \(\operatorname{Sol} \gets \operatorname{Sol} \cup \{S_i\}\) (добавляем выбранное множество в решение)
• возврат \(\operatorname{Sol}\)

На каждой итерации выбираем самое эффективное множество, удаляем покрытые элементы и продолжаем до тех пор, пока не будут покрыты все элементы. Пусть \(C\) – это множество элементов, уже покрытых на предыдущих итерациях. Для каждого множества \(S_{i}\) определим его эффективность как \(\alpha_{i}=\frac{c\left(S_{i}\right)}{\left|S_{i} \setminus C\right|}\). Эффективность множества равна средней стоимости, с которой покрываются элементы этого множества, еще не покрытые на предыдущих итерациях. Ценой элемента назовем среднюю стоимость, с которой он был покрыт. Для всех вновь покрытых элементов множества \(S_{i}\) цена будет одинаковой.

Лемма 1 Пусть \(S \in \mathcal{S}\) – произвольное подмножество. Занумеруем элементы \(S\) в том порядке, в котором они были покрыты (“куплены”) жадным алгоритмом: \(u_1, u_2, \ldots , u_l \in S\). Тогда \[ \operatorname {price}(u_j) \leq \frac{c(S)}{l-j+1}, \qquad j \in \left\{ 1, \ldots , l\right\} \]

Mn-proofДоказательство

Рассмотрим итерацию, на которой был покрыт элемент \(u_j\).

• К этой итерации покрыто не больше \(j-1\) элементов из \(S\);

• Не покрыто как минимум \(l - (j-1)\) элементов \(S\);

• Значит, если бы на этой итерации алгоритм взял в \(\operatorname {Sol}\) само множество \(S\), эффективность была бы не выше \(\frac{c(S)}{l-(j-1)}\);

• Алгоритм же выбирает множество с минимальной эффективностью, поэтому назначенная цена не больше: \(\operatorname {price}(u_j) \leq \frac{c(S)}{l-j+1}\).

Для натурального \(n \in \mathbb {N}\) обозначим

\[ H_n := 1 +\frac{1}{2}+\frac{1}{3}+\ldots +\frac{1}{n} \]

частичную сумму гармонического ряда. Заметим, что \(H_n = \ln n + \gamma + o(1)\), где \(\gamma \approx 0.577\) – постоянная Эйлера; в частности, \(\ln n < H_n \leq \ln n + 1\).

Следствие 1 Для произвольного \(S \in \mathcal{S}\) \[ \operatorname {price}(S) = \sum _{j=1}^l \operatorname {price}(u_j) \leq c(S) \cdot H_l \] где \(l = \left|S\right|\).

Mn-proofДоказательство

Имеем \[ \operatorname {price}(S) = \sum _{j=1}^l \operatorname {price}(u_j) \leq \sum _{j=1}^l \frac{c(S)}{l-(j-1)} = c(S)H_l \]

Теорема 1 Алгоритм Хватала является \(H_{\tilde{n}}\)-приближенным алгоритмом для задачи о покрытии, где \(\tilde{n}\) – это мощность самого большого множества из \(\mathcal{S}\). В частности, он является \(H_n\)-приближенным алгоритмом, где \(n\) – это количество элементов в \(U\).

Mn-proofДоказательство

Пусть \(\sigma^* = \left\{ S_{i_1}, \ldots , S_{i_{k^*}}\right\}\) – это оптимальное решение. Его стоимость: \(\operatorname {OPT} = \sum_{m=1}^{k^*} c(S_{i_m})\). Пусть \(\sigma_{\operatorname {GA}}\) – это результат работы жадного алгоритма. Имеем \[ \operatorname {price}(\sigma _{\operatorname {GA}}) = \sum _{u\in U}\operatorname {price}(u) \leq \sum _{m=1}^{k^*} \operatorname {price}(S_{i_m}) \leq \sum _{m=1}^{k^*} c(S_{i_m}) \cdot H_{\left|S_{i_m}\right|} = \operatorname {OPT} \cdot H_{\tilde{n}} \]

Точный пример к алгоритму Хватала

\(n\) одноэлементных множеств с весами \(\frac1n,\frac1{n-1},\dots,1\) внутри одного множества веса \(1+\varepsilon\), содержащего все элементы. На каждой итерации жадный алгоритм берёт множество с наименьшей ценой за непокрытый элемент — и это всегда очередное одноэлементное множество: его цена \(\frac1{n-i+1}\) чуть меньше цены большого, \(\frac{1+\varepsilon}{n-i+1}\). Пройдите итерации кнопками или задайте \(n\).

\(n=\)5

Можно ли получить лучший алгоритм? Нет: задача покрытия множествами не может быть аппроксимирована с коэффициентом \((1 - o(1))\ln (n)\).

2 Задача о вершинном покрытии наименьшего веса

2.1 Использование алгоритма для покрытия множествами

Заметим, что задача о вершинном покрытии наименьшего веса (в частности, наименьшей мощности) является частным случаем задачи о покрытии множествами. Действительно, пусть задан граф \(G=(V, E)\), и требуется найти вершинное покрытие минимального веса. Можно построить следующий экземпляр задачи о покрытии множествами:

• Универсум \(U\) сопоставим с множеством рёбер \(E\), т.е. \(U = E\).

• Каждая вершина \(v \in V\) соответствует множеству \(S_v \subseteq U\), состоящему из всех рёбер, инцидентных вершине \(v\).

• Функция стоимости \(c: S_v \mapsto \text{вес вершины } v\).

Тогда любое покрытие множествами \(S' \subseteq \{ S_v : v \in V\}\), покрывающее \(U\), соответствует выбору вершин \(V' \subseteq V\), образующих вершинное покрытие графа. Минимизация суммарного веса выбранных множеств \(S'\) эквивалентна минимизации веса вершинного покрытия.

Заметим, что жадный алгоритм для задачи о вершинном покрытии наименьшей мощности – это частный случай алгоритма Хватала. Таким образом, у нас есть его оценка точности: \(H_{\tilde{n}}\), где \(\tilde{n}\) – это максимальная степень вершины в \(G\).

2.2 Алгоритмы константной точности через расщепление весов графа

Во введении мы получили алгоритм для задачи о вершинном покрытии наименьшей мощности с фиксированной точностью, равной \(2\). Будет ли он работать с такой же точностью, но для более общей задачи, т.е. задачи о покрытии наим. веса? Нет!

Покрытие наименьшего веса не сводится к покрытию наименьшей мощности

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

2.2.1 Алгоритм локальных весов

От англ. local ratio algorithm.

Идея алгоритма локальных весов: расщепление \(w=w_1+w_2\)

Выбираем ребро \(\{v,v'\}\), инцидентное самой дешёвой вершине, и вычитаем \(c=\min(w(v),w(v'))\) с обоих его концов: \(w_1\) сосредоточен на этих двух вершинах (по \(c\) на каждой, остальное — 0), а \(w_2=w-w_1\) — исходный граф с уменьшенными весами. Любое покрытие графа \((V,E,w_1)\) — 2-приближение: хотя бы одну из двух вершин ребра покрыть придётся. Наведите курсор на вершину, чтобы проследить её вес по трём панелям.

=

+

концы выбранного ребравес стал нулём

Полный прогон алгоритма локальных весов

На каждом шаге \(i\) алгоритм берёт ребро, инцидентное самой дешёвой из ещё ненулевых вершин, и вычитает \(c\) с обоих его концов — вес \(t_i\) сосредоточен на этих двух вершинах. После 5 шагов остаток \(t_6\) отмечает обведённые вершины — это решение алгоритма. Наведите курсор на вершину, чтобы увидеть её остаток.

=

Теорема 2 (О разделении графа) Пусть дан граф \((V,E)\), функция весов вершин \(w: V \to \mathbb {R}_+\), и пусть весовая функция распалась на сумму функций: \(w = w_1 + w_2\). Если \(V' \subset V\) – вершинное покрытие, являющееся \(\rho\)-аппроксимацией оптимального покрытия и для \((V,E,w_1)\), и для \((V,E,w_2)\), то \(V'\) будет \(\rho\)-аппроксимацией и для исходного графа со взвешенными вершинами \((V,E,w)\).

Mn-proofДоказательство

Пусть \(V^*\), \(V^*_1\), \(V^*_2\) – оптимальные покрытия для графа \((V,E)\) с функциями весов \(w\), \(w_1\), \(w_2\) соотв. Нам дано: \[ \begin{align} w_1(V') & \leq \rho w_1(V^*_1) \leq \rho w_1(V^*) \\ w_2(V') & \leq \rho w_2(V^*_2) \leq \rho w_2(V^*) \\ \end{align} \] Получаем \[ w(V') = w_1(V') + w_2(V') \leq \rho \left(w_1(V^*) + w_2(V^*)\right) = \rho w(V^*) \]

2.2.2 Уровневый алгоритм

Второй способ расщеплять веса: делать это глобально, а не для каждого ребра по отдельности.

Назовем функцию \(w: V \to \mathbb {Q}_+\), соответствующую весам вершин, пропорционально-степенной, если существует константа \(c>0\), такая, что вес каждой вершины \(v \in V\) равен \(w(v) = c \cdot \operatorname {deg}(v)\).

Уровневый алгоритм: другой способ расщепления весов

Глобальное вычитание пропорционально степени вершины: \(c=\min_v w(v)/\deg(v)=3{,}5\) (достигается на вершине \(ML\), \(\deg=4\)), поэтому \(w_1(v)=c\cdot\deg(v)\) для каждой вершины, а \(w_2=w-w_1\) — остаточная функция (на \(ML\) остаток равен \(0\)). Наведите курсор на вершину: степень и все три веса.

=

+

w₁ = 3,5·deg — минимум w/degостаток 0

Лемма 2 Пусть \(w: V \rightarrow \mathbf{Q}^{+}\) является пропорционально-степенной функцией. Тогда \[ w(V) \leq 2 \operatorname {OPT} \]

Mn-proofДоказательство

Пусть \(c>0\) – константа, такая, что \(w(v)=c \cdot \operatorname {deg}(v)\). Пусть \(U\) – оптимальное вершинное покрытие в графе \(G\). Поскольку \(U\) покрывает все ребра, то: \[ \sum _{v \in U} \operatorname {deg}(v) \geq |E| \] Из этого следует, что \(w(U) \geq c|E|\). Вспоминая, что \(\sum_{v \in V} \operatorname {deg}(v)=\) \(2|E|\), получим \(w(V)=2 c|E|\). Итого \(w(V) = 2c\left|E\right| \leq 2 w(U) = 2\operatorname {OPT}\).

Пусть \(w: V \rightarrow \mathbf{Q}^{+}\) – произвольная функция. Определим наибольшую пропорционально-степенную функцию относительно \(w\) в графе \(G\) следующим образом:

1. Удалим из графа все вершины степени 0;

2. Среди оставшихся вершин вычислим величину \(c=\min \left\{ \frac{w(v)}{\operatorname {deg}(v)}\right\}\).

Тогда функция \(t(v)=c \cdot \operatorname {deg}(v)\) – искомая.

Определим через \(w^{\prime }(v)=w(v)-t(v)\) остаточную функцию весов.

Представим алгоритм, который разбивает исходную весовую функцию на пропорционально-степенные функции и строит вершинное покрытие.

Algorithm 2 Уровневый алгоритм для задачи вершинного покрытия с весами (\(G=(V, E), w: V \rightarrow \mathbb {Q}^{+}\))

• \(\operatorname{Sol} \gets \varnothing\), \(i \gets 0\)
• \(w'(v) \gets w(v)\) для всех \(v \in V\) (инициализация остаточных весов)
• \(D_0 \gets \{v \in V \mid \deg(v) = 0\}\) (вершины степени \(0\) не участвуют в покрытии)
• \(V_0 \gets V \setminus D_0\) (удаляем вершины степени \(0\))
• пока \(V_i \neq \varnothing\) выполнять
  • \(c \gets \min_{v \in V_i} \frac{w'(v)}{\deg_i(v)}\) (\(\deg_i\) – степень в текущем подграфе \(G_i = G[V_i]\))
  • для каждого \(v \in V_i\) выполнять
    • \(t_i(v) \gets c \cdot \deg_i(v)\) (вычитаемая величина для вершины)
    • \(w'(v) \gets w'(v) - t_i(v)\) (обновляем остаточный вес)
  • \(W_i \gets \{v \in V_i \mid w'(v) = 0\}\) (вершины, достигшие нулевого остаточного веса)
  • \(\operatorname{Sol} \gets \operatorname{Sol} \cup W_i\) (добавляем вершины в решение)
  • \(V_{i+1} \gets V_i \setminus W_i\)
  • \(D_{i+1} \gets \{v \in V_{i+1} \mid \deg_{G[V_{i+1}]}(v) = 0\}\) (вершины степени \(0\) после удаления \(W_i\))
  • \(V_{i+1} \gets V_{i+1} \setminus D_{i+1}\) (удаляем вершины степени \(0\))
  • \(i \gets i + 1\)
• возврат \(\operatorname{Sol}\)

2.2.3 Оценки точности

Теорема 3 Алгоритм локальных весов и уровневый алгоритм являются \(2\)-приближенными алгоритмами для задачи о вершинном покрытии.

Mn-proofДоказательство

Докажем утверждение для уровневого алгоритма. Пусть \(t_{0}, \ldots , t_{k-1}\) – пропорционально-степенные функции на графах \(G_{0}, \ldots , G_{k-1}\), построенные алгоритмом. Тогда \(\operatorname {Sol}=W_{0} \cup \ldots \cup W_{k-1}\) – решение, полученное алгоритмом, и \(V \backslash \operatorname {Sol}=D_{0} \cup \ldots \cup D_{k}\).

Сначала покажем, что множество \(\operatorname {Sol}\) является вершинным покрытием для графа \(G\). Предположим, что это не так. Тогда существует ребро \((u, v)\), такое, что \(u \in D_{i}, v \in D_{j}\) для некоторых \(i, j\). Пусть \(i \leq j\); вершина \(v\) удаляется позже, поэтому в момент \(i\) обе вершины еще присутствуют, и ребро \((u, v)\) лежит в \(G_{i}\). Это противоречит тому, что степень \(u\) в \(G_i\) равна нулю.

Пусть \(C^{*}\) – оптимальное вершинное покрытие. Докажем, что \(w(\operatorname {Sol}) \leq 2 \cdot \operatorname {OPT}\). Рассмотрим вершину \(v \in \operatorname {Sol}\). Пусть \(v \in W_{j}\) для некоторого \(j\); ее остаточный вес обнулился, поэтому

\[ w(v)=\sum _{i \leq j} t_{i}(v) \]

Теперь рассмотрим вершину \(v \in V \backslash \mathrm{Sol}\). Пусть \(v \in D_{j}\) для некоторого \(j\); остаточный вес неотрицателен, поэтому

\[ w(v) \geq \sum _{i<j} t_{i}(v) \]

Заметим, что в каждом слое \(i\) множество вершин \(C^{*} \cap V_{i}\) является покрытием для \(G_{i}\), поскольку \(G_{i}\) – вершинно-индуцированный подграф (\(C^*\) покрывает каждое ребро \(G_i\), причем покрывающий конец сам лежит в \(V_i\)). Применяя к пропорционально-степенной функции \(t_i\) на графе \(G_i\) лемму выше, получаем \(t_{i}\left(\operatorname {Sol} \cap V_{i}\right) \leq t_i(V_i) \leq 2 \cdot t_{i}\left(C^{*} \cap V_{i}\right)\). Окончательно:

\[ w(\operatorname {Sol}) = \sum _{i=0}^{k-1} t_{i}\left(\mathrm{Sol} \cap V_{i}\right) \leq 2 \sum _{i=0}^{k-1} t_{i}\left(C^{*} \cap V_{i}\right) \leq 2 \cdot w\left(C^{*}\right) \]

(в первом равенстве вес каждой вершины \(v \in W_j\) разложен по слоям \(i \leq j\), а в последнем неравенстве использовано, что для любой вершины \(\sum_{i \colon v \in V_i} t_i(v) \leq w(v)\)).

Для алгоритма локальных весов оценка следует из теоремы о разделении графа: на каждом шаге вычитаемая весовая функция \(w_1\) сосредоточена на концах одного ребра \((u,v)\) (по \(\varepsilon\) на каждом), и любое вершинное покрытие имеет \(w_1\)-вес не меньше \(\varepsilon\), тогда как \(w_1\)-вес любого множества вершин не больше \(2\varepsilon\) – т.е. относительно каждой из вычитаемых функций произвольное покрытие является \(2\)-аппроксимацией. Решение алгоритма составлено из вершин с нулевым остаточным весом, поэтому его вес равен сумме весов по вычитаемым функциям, и по теореме о разделении оно является \(2\)-аппроксимацией для исходных весов.

Приведем пример, на котором достигается эта оценка. Пусть задан полный двудольный граф \(K_{n, n}\), в котором все вершины имеют единичные веса. Алгоритм Уровневый возьмет в покрытие все \(2n\) вершин графа \(K_{n, n}\), тогда как оптимальное решение состоит из вершин одной доли.

3 Задачи

ProblemЗадача 1

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

ProblemЗадача 2

Постройте пример, на котором достигается оценка Алгоритма Хватала для задачи о покрытии множествами, даже если вес каждого множества равен 1.

ProblemЗадача 3

Рассмотрим экземпляры задачи о покрытии, в которых каждый элемент входит не больше чем в \(3\) подмножества. Постройте для таких примеров \(3\)-приближенный уровневый алгоритм.

ProblemЗадача 4

Полным антисимметрическим графом называется ориентированный граф \(G=(V, E)\), в котором для любой пары вершин \(u, v \in V\) существует ровно одна из дуг \((u, v) \in E\) либо \((v, u) \in E\). Обратным вершинным покрытием в \(G\) называется множество вершин, после удаления которых граф становится ациклическим. Предложите \(3\)-приближенный алгоритм для поиска обратного вершинного покрытия в антисимметрическом графе.

HintПодсказка

Покажите, что для этого достаточно убить циклы длины 3.