최대 일대 다 일치

Question

허락하다 $G = (X+Y,E)$ 이분 그래프이고 $k\geq 1$정수. 최대$k$-매칭 은$E$ 각 꼭지점 $X$ 최대 인접 $k$ 가장자리와 각 정점 $Y$ 최대 인접 $1$ 가장자리.

최대 카디널리티 $k$-매칭은 다음 알고리즘으로 찾을 수 있습니다.

• 창조하다 $k$ 각 정점의 사본 $x\in X$, 각 사본이의 모든 인접 항목에 인접하도록 $x$ 에 $Y$.
• 결과 그래프에서 최대 일치를 찾습니다.

그래프에 대한 런타임 복잡성 $n$ 정점 및 $m$ Hopcroft-Karp 알고리즘을 사용하는 모서리는 $O(k m\sqrt{k n}) =O(k^{3/2}\cdot m\sqrt{n})$.

다음 대체 알고리즘에 관심이 있습니다.

• 반복 $k$ 타임스:

  • 최대 일치 항목 찾기 $G$.
  • 일치하는 정점 제거 $Y$ 그래프에서.

런타임 복잡성은 다음과 같습니다. $O(k \cdot m\sqrt{n})$.

하지만이 알고리즘은 항상 최대 값을 찾습니다. $k$-어울리는?

Answer 1

아니요. 여기에 반례가 있습니다. $X=\{a,b\}, Y=\{c,d,e,f\}, E=\{ac, ad, ae, be, bf\}, k=2$. 알고리즘의 첫 번째 반복은$\{ae,bf\}$ (특히 가장자리 $ae$), 솔루션이 존재하더라도 찾을 수 없음 : $\{ac, ad, be, bf\}$.