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

Задача:

Даны матроиды [math]M_1 = (S, \mathcal{I}_1), \ldots ,(S, \mathcal{I}_k)[/math]. Необходимо найти максимальное по мощности независимое множество в объединении [math]M_1\ldots M_k[/math].

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

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

Алгоритм

Эта задача сводится к пересечению матроидов, однако есть другой способ её решить. Пусть [math]I_i \in \mathcal{I}_i[/math], для [math]i = 1\ldots k[/math] с [math]I_i \cap I_j = \emptyset[/math], если [math]i \neq j[/math]. Определим граф замен: для каждого [math]M_i[/math] построим двудольный ориентированный граф [math]D_{M_i}(I_i)[/math] так, что в левой доле находятся вершины из [math]I_i[/math], а в правой — вершины из [math]S \setminus I_i[/math]. Построим ориентированные ребра из [math]y \in I_i[/math] в [math]x \in S \setminus I_i[/math], при условии, что [math](I_i \setminus y) \cup x \in \mathcal{I}_i[/math].

Объединим все [math]D_{M_i}(I_i)[/math] в один граф [math]D[/math], который будет суперпозицией ребер из этих графов. Пусть для каждого [math]i:[/math] [math]F_i[/math] — множество элементов [math]s \notin I_i[/math] с [math]I_i \cup {s} \in \mathcal{I}_i[/math]. Определим [math]I = I_1 \cup \ldots \cup I_k[/math], [math]F = F_1 \cup \ldots \cup F_k[/math] и [math] \mathcal{I} = \mathcal{I}_1 \cup \ldots \cup \mathcal{I}_k[/math].

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

Псевдокод

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

Время работы

Это подразумевает, что максимальное независимое множество в [math] \mathcal{I} = \mathcal{I}_1 \cup \ldots \cup \mathcal{I}_k[/math] мы можем найти за полиномиальное время (жадно наращивать независимое множество в [math]M = M_1 \cup \ldots \cup M_k[/math]). Cunningham разработал алгоритм, которым за [math]O((n^{(3/2)} + k)mQ + n^{(1/2)}km)[/math] можно найти максимальное независимое множество в [math] \mathcal{I} = \mathcal{I}_1 \cup \ldots \cup \mathcal{I}_k[/math], где [math]n[/math] максимальный размер множества в [math] \mathcal{I} = \mathcal{I}_1 \cup \ldots \cup \mathcal{I}_k[/math], [math]m[/math] размер подмножества и [math]Q[/math] время, необходимое, чтобы определить принадлежит ли множество [math] \mathcal{I}_j[/math] для каждого [math]j[/math]. Более детальное объяснение алгоритма (но не время работы) можно найти у C. Greene и T.L. Magnanti.

Теорема:

Для любого [math]s \in S \setminus I[/math] имеем [math]I \cup s \in \mathcal{I} \Leftrightarrow [/math] существует ориентированный путь из [math]F[/math] в [math]s[/math] по ребрам графа [math]D[/math].

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

См. также

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

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

Michel X. Goemans. Advanced Combinatorial Optimization. Lecture 13

Alexander Schrijver. Combinatorial Optimization. Polyhedra and Efficiency, Volume A-C, — Springer, 2004, — стр.732

C. Greene, T.L. Magnanti, Some abstract pivot algorithms, SIAM Journal on Applied Mathematics 29 (1975) 530-539