Максимальное сопоставление одного ко многим

Question

Пусть $ g= (x + y, e) $ - бипарттаный график и $ k \ geq 1 $ целое число. MAXIME $ k $ - -matching - это подмножество $ e $ в Каждая вершина $ x $ составляется с большинством $ K $ ребра и каждая вершина $ y $ соседствует с большинством $ 1 $ Edge.

Максимальная кардинальность $ K $ - можно найти следующим алгоритмом:

.
• Создать $ K $ Копии каждой вершины $ x \ in x $ , так что каждая копия соседствует со всеми соседями $ x $ в $ y $ .
• Найти максимальное соответствие в результирующем графике.

Его сложность работы для графа с $ n $ вершины и $ m $ ребра, Используя алгоритм Hopcroft-Karp, это $ o (km \ sqrt {kn})= o (k ^ {3/2} \ cdot m \ sqrt {n}) $ .

Я заинтересован в следующем альтернативном алгоритме:

.

• повторить $ k $ Times:

  .
  • Найти максимальное сопоставление в $ g $ .
  • Удалите соответствующие вершины $ y $ с графика.

Его сложность работы - $ O (k \ cdot m \ sqrt {n}) $ .

Но всегда ли этот алгоритм находит максимальный $ K $ -MATCHING?

Answer 1

нет.Вот контрпример: $ x={a, b \}, y={c, d, e, f \}, e={ac, ac, ae,быть, bf \}, k= 2 $ .Первая итерация вашего алгоритма может выбрать $ \ {ae, bf \} $ (в частности, край $ AE $ $), предотвращая их быть найденным решением, хотя нужно существовать: $ \ {ac, ad, be, bf \} $ .