Алгоритм построения базы в объединении матроидов

Задача:

Даны матроиды $M_1 = \langle S, \mathcal{I}_1 \rangle$ и $M_2 = \langle S, \mathcal{I}_2 \rangle$. Необходимо найти максимальное по мощности независимое множество в объединении $M_1$ и $M_2$.

Определение:

Объединение матроидов (англ. matroid union) $M$ = $\langle S,\mathcal{I} \rangle$ = $\bigcup\limits_{k=1}^{n}$ $M_i$, где $M_i$ = $\langle S,\mathcal{I}_i \rangle$

Алгоритм

Определим граф замен: для каждого $M_i$ построим двудольный ориентированный граф $D_{M_i}(I_i)$, где $I_i \in \mathcal{I}_i$, такой что в левой доле находятся вершины из $I_i$, а в правой — вершины из $S \setminus I_i$. Построим ориентированные ребра из $y \in I_i$ в $x \in S \setminus I_i$, при условии, что $(I_i \setminus y) \cup x \in \mathcal{I}_i$.

Объединим все $D_{M_i}(I_i)$ в один граф $D$, который будет суперпозицией ребер из этих графов. Пусть для каждого $i:$ $F_i$ - множество вершин из $S_i \setminus I_i$, которые могут быть добавлены в $I_i$ таким образом, что $I_i + x$ независимое множество в $M_i$. Или формально:

$F_i = \{ x \in S \setminus I_i : I_i + x \in \mathcal{I}_i \}$. $F$ = $\bigcup\limits_{k=1}^{n}$ $F_i$

Нам известно, что объединение матроидов — матроид. При поиске базы матроида используется жадный алгоритм. На каждом шаге мы выбираем элемент не из текущего множества в новом графе замен $D_{M_i}(I_i)$ (следующая теорема отвечает на вопрос, как представить это в графе). Здесь мы обозначим текущее множество как $I$. Тогда нужно найти такой элемент $s \in S \setminus I$, что $I + s$ — снова независимо. Все наши кандидаты находятся в $S \setminus I$. Если мы найдем путь из $F$ в $S \setminus I$, то элемент $s$, которым путь закончился, можно будет добавить в $I$. То есть шаг жадного алгоритма заключается в создании нового $D$ и поиске такого пути.

Псевдокод

 $J$ = $\emptyset$
 for $i \leftarrow 0$ to $n - 1$
     построить граф замен $D_{M_i}(I_i)$
     if $I_i + x \in \mathcal{I}_i$
         $J \leftarrow I_i + x$

Теорема:

Для любого $s \in S \setminus I$ имеем $I + s \in J \Leftrightarrow$ существует ориентированный путь из $F$ в $s$ по ребрам $D$.

Доказательство:

$\triangleright$

$\Leftarrow$ Пусть существует путь из $F$ в $s$ и $P$ — самый короткий такой путь. Запишем его вершины как {$s_0, s_1, ... s_p$}. $s_0 \in F$, так что не умаляя общности можно сказать, что $s_0 \in F_1$. Для каждого $j = 1...k$ определим множество вершин $S_j =$ {$s_i, s_{i+1}:(s_i, s_{i+1}) \in D_{M_j}(I_j)$}, где $i$ пробегает от $0$ до $p - 1$. Положим, что $I'_1 = (I_1 \oplus S_1) \cup \{s_0\}$, для всех $j \gt 1$ положим $I'_j = (I_j \oplus S_j)$. Ясно, что $\cup _j I'_j = I + s$. Для того, чтобы показать независимость $I + s$ в объединении матроидов нужно показать, что $I'_j \in J_j$ для всех $j$. Заметим, что так как мы выбирали путь $P$ таким, что он будет наименьшим, для каждого $j \gt 1$ существует единственное паросочетание между элементами, которые мы добавляли и удаляли, чтобы сконструировать $I'_j = I_j \oplus S_j$. Так как паросочетание единственно, $I'_j \in J_j$. Аналогично $s_0 \in F_1$, значит $I'_1 \in J_1$. Следовательно $I + s$ независимо в объединении матроидов. $\Rightarrow$ Пусть нет пути из $F$ в $s$ по ребрам $D$. Тогда пусть существует множество $T$, состоящее из вершин $D$, из которого мы можем достичь $s$ : $T = \{x, \exists x \leadsto s\}$ по допущению $F\cap T = \varnothing$. Утверждается, что для всех $i : |I_i \cap T| = r_i(T)$(что означает, что $I_i \cap T$ — максимальное подмножество $T$, независимое в $M_i$). Предположим, что это не так. $|I_i \cap T| = r_i(I_i\cap T) \le r_i(T)$, это возможно только если $|I_i \cap T| \lt r_i(T)$. Значит существует такой $x \in T \cap (S \setminus I_i)$, для которого $(I_i \cap T) + x \in J_i$. Но $x \notin F$ (по предположению вначале доказательства), значит $I_i + x \notin J_i$. Из этого следует, что $I_i + x$ содержит единственный цикл. Значит существует $y \in I_i - T$, такой что $I_i + x - y \in J_i$. Получается, что $(y, x)$ — ребро в $D_{M_i}(I_i)$ и оно содержит этот $y \in T$, что противоречит тому как был выбран $y \in I_i \setminus T$. Следовательно для всех $i$ нам известно : $|I_i \cap T| = r_i(T)$. У нас есть $s \in T$ и $(I + s) \cap T = (\cup I_i + s)\cap T = \cup(I_i \cap T) + s$. Из определния функции ранга объединения матроидов имеем : $r_M(I + s) \le (|(I + s)\setminus T| + \sum\limits_{k=1}^{n}r_i(T))$ $r_M(I + s) \le |(I + s)\setminus T| + \sum\limits_{k=1}^{n} |I_i \cap T| = |I\setminus T| + \sum\limits_{k=1}^{n} |I_i \cap T| = |I| \lt |I + s|$ и значит $(I + s) \notin J$ — противоречие.

$\triangleleft$

См. также

• Пересечение матроидов, определение, примеры
• Алгоритм построения базы в пересечении матроидов

Источники информации

Michel X. Goemans. Advanced Combinatorial Optimization. Lecture 13