Участник:Qtr/2

Задача:

Даны матроиды [math]M_1 = \langle S_1, \mathcal{I}_1 \rangle \dots M_n = \langle S_n, \mathcal{I}_n \rangle[/math]. Необходимо найти максимальное по мощности независимое множество в объединении [math]\bigcup\limits_{i=1}^{n}[/math] [math]M_i[/math].

Алгоритм

Пусть у нас есть множество [math]I\in\mathcal{I}[/math], где [math] \mathcal{I} = \{ \bigcup\limits_{i=1}^{n} I_i \mid I_i \in \mathcal{I}_i\} [/math], и разбиение [math]I[/math] на [math]\bigcup\limits_{i=1}^{n}I_i[/math], такое, что [math]I_i\in \mathcal{I}_i[/math]. То есть, [math]I[/math] состоит из каких-то подмножеств семейства множеств [math]\mathcal{I}_i[/math] для [math]i[/math] от [math]1[/math] до [math]n[/math]. Рассмотрим элемент [math]s\not \in I[/math]. Нужно определить, правда ли, что [math]I+s\in \mathcal{I}[/math]. Если научиться это делать, то тогда можно решить задачу жадным алгоритмом, добавляя в текущее множество по одному элементу [math]s[/math] на каждом шаге.

Определим объединение матроидов как [math]M[/math] = [math]\langle S,\mathcal{I} \rangle[/math] = [math]\bigcup\limits_{i=1}^{n}[/math] [math]M_i[/math], где [math]M_i[/math] = [math]\langle S_i,\mathcal{I}_i \rangle[/math].

Для [math]i[/math] от [math]1[/math] до [math]n[/math] возьмем [math]M_i[/math] и построим двудольный ориентированный граф [math]D_{M_i}(I_i)[/math], где [math]I_i \in \mathcal{I}_i[/math]. Вершины графа — элементы из [math]S[/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] D_{M_i}(I_i)[/math].

Для каждого [math]i[/math] определим множество [math]F_i[/math] как множество вершин [math]S_i\setminus I_i[/math] таких, что множество [math]I_i+x[/math] также независимое. Формально: [math]F_i = \{ x \in S_i \setminus I_i \mid I_i + x \in \mathcal{I}_i \}[/math].

Определим [math]F[/math] = [math]\bigcup\limits_{k=1}^{n}[/math] [math]F_i[/math]

Теорема:

Для какого-нибудь [math]s \in S \setminus I[/math] выполняется: [math]I + 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, \dots s_p\}[/math]. Вершина [math]s_0 \in F[/math], так что не умаляя общности можно сказать, что [math]s_0 \in F_1[/math]. Для каждого [math]j = 1\dots n[/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 \mathcal{I}_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 \mathcal{I}_j[/math]. Аналогично [math]s_0 \in F_1[/math], значит [math]I'_1 \in \mathcal{I}_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\mid \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 \mathcal{I}_i[/math]. Но [math]x \notin F[/math] (по предположению в начале доказательства), значит [math]I_i + x \notin \mathcal{I}_i[/math]. Из этого следует, что [math]I_i + x[/math] содержит единственный цикл. Значит существует [math]y \in I_i - T[/math], такой, что [math]I_i + x - y \in \mathcal{I}_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 \mathcal{I}[/math] — противоречие.

[math]\triangleleft[/math]

Итак, теперь мы можем описать сам алгоритм. Изначально инициализируем [math]I[/math] как семейство пустых множеств. На каждом шаге будем строить граф [math]D[/math] из текущего [math]I[/math] и [math]S\setminus I[/math] и добавлять в [math]I[/math] кандидата-вершину [math]s[/math], удовлетворяющую условию теоремы. При добавлении вершины нужно не забыть поменять местами вершины на пути [math]F \leadsto s[/math], так как ребра из [math]I_i[/math] должны вести в [math]S\setminus I_i[/math] (т.е. должен сохраняться инвариант). Когда вершины-кандидаты закончатся, по доказанной выше теореме получившееся множество [math]I[/math] станет максимальным.

Псевдокод

В реализации алгоритма каждый элемент представлен целым числом.

• [math]s[/math] — принимаемое множество носитилей матроидов
• [math]\mathtt{base}[/math] — принимаемое множество баз матроидов
• [math]\mathtt{res}[/math] — возвращаемая база в объединении матроидов. [math]res_1, res_2 \dots res_n[/math] содержат элементы, содержащиеся в полученной базе.

int[][] unionBase(int[n] [math]s[/math], int[n] [math]\mathtt{base}[/math]):
  int[n][] [math]\mathtt{res}[/math] // На каждом шаге алгоритма заполняем очередным элементом 
  bool [math]\mathtt{reached}[/math] = false // Индикатор окончания работы цикла. Если true, то не нашли подходящую вершину
  while [math]!\mathtt{reached}[/math]
    [math]\mathtt{reached}[/math] = true
    int [math]f[n][/math] // Соответствует [math]F[/math] 
    Graph [math]d[n][/math]
    for [math]i[/math] = 1 to [math]n[/math]
      [math]d[i][/math] = buildBipartiteGraph[math](\mathtt{res[i]} ,s[i] \setminus \mathtt{res}[i])[/math] // Строим двудольный граф d[i] 
      [math]f[i][/math] = [math] \{ x \in s[i] \setminus \mathtt{res[i]} : \mathtt{res}[i] + x \in base[i] \}[/math] 
    for [math]\mathtt{elem} \in s\setminus \mathtt{base}[/math]
      List<int> [math]p[/math] = findShortestPath([math]f[/math], [math]\mathtt{elem}[/math])
      if [math]p\neq \varnothing [/math]
        [math]\mathtt{reached}[/math] = false // Нашли очередную вершину, цикл можно продолжить 
        int [math]\mathtt{pos}[/math] = getF([math]p[1][/math]) // Находим [math]f_i[/math], которому принадлежит стартовая вершина в пути
        int [math]v[n][/math] // i-й элемент [math]v[/math] хранит множество вершин, соответствующее i-му входному матроиду 
        for [math] j[/math] = 1 to [math]p.len - 1[/math]
          int [math]\mathtt{vertex}[/math] = getDbyEdge[math](p[j],p[j+1])[/math] // Находим номер графа, соответствующего ребру [math](p[j],p[j+1])[/math] 
          [math]v[\mathtt{vertex}].add(j)[/math] // Добавляем в соответствующее вершинам множество концы ребра
          [math]v[\mathtt{vertex}].add(j + 1)[/math]
        for [math]j[/math] = 1 to [math]n[/math]
          [math] \mathtt{res}[j][/math] = [math] \mathtt{res}[j] \oplus v[j][/math]  // Удаляем и добавляем ребра на пути к конечной вершине  
        [math]\mathtt{res}[\mathtt{pos}][/math] = [math]res[\mathtt{pos}] \cup p[1] [/math]
        break
  return [math]\mathtt{res}[/math]

См. также

• Объединение матроидов, проверка множества на независимость
• Объединение матроидов, доказательство того, что объединение является матроидом
• Пересечение матроидов, определение, примеры

Асимптотика

На каждом шаге алгоритма происходит построение графа D. Для того, чтобы его построить, нам нужно для [math]i=1\dots n[/math] для каждого [math]v[/math] из [math]S[/math] и [math]u[/math] из [math]S\setminus I_i[/math], где [math]S[/math] — объединение матроидов, проверить условие [math](I_i \setminus u) \cup v \in \mathcal{I}_i[/math]. Построение графа занимает [math]O(\sum\limits_{i=1}^{n}\vert (S_i\setminus I_i)\vert \vert I_i\vert [/math]) времени на каждой итерации. Нахождение кратчайшего пути для всех вершин занимает [math]O(\vert E\vert )[/math] единиц времени, где [math]E[/math] — множество ребер графа [math]D[/math], если использовать поиск в ширину, что в худшем случае будет равно [math]O(\vert S \vert ^2)[/math]. Обновление [math]res[/math] занимает [math]O(n|I_{max}|)[/math] времени, что равно [math]O(\vert S \vert)[/math]. В худшем случае требуется [math]|S|[/math] итераций, и общая асимптотика будет [math]O(|S|^3)[/math].

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

• Michel X. Goemans. Advanced Combinatorial Optimization. Lecture 13