algorithm - SPOJ-DIVREL でアンチチェーン要素を取得するにはどうすればよいですか?

Question

問題: http://www.spoj.com/problems/DIVREL

問題は、与えられた要素の集合から、倍数でない (b 形式で割り切れる) 要素の最大数を見つけることだけです。要素からその倍数へのエッジを作成してグラフを作成すると、それは DAG になります。

ここで問題は、ディルワースの定理を使用してアンチチェーンのカーディナリティに等しいすべての頂点を含むチェーンの最小数を見つけることに変わります。これは部分的に順序付けられたセットであるためです。

最小チェーンは二部マッチングを使用して見つけることができます (方法: 最小パス カバーです) が、アンチチェーン要素自体を見つけることができませんか?

Answer 1

アンチチェーンを計算するには、次のことができます。

1. a が b を除算する場合にのみ、LHS a から RHS b へのエッジを持つ新しい 2 部グラフ D で、最大 2 部マッチング (たとえば、最大フロー アルゴリズムを使用) を計算します。
2. マッチングを使用して、最小の頂点カバーを計算します (たとえば、Konig の定理の証明で説明されているアルゴリズムを使用)
3. アンチチェインは、頂点カバーにないすべての頂点によって与えられます

このような 2 つの要素間にエッジがあってはなりません。そうしないと、頂点カバーによって覆われていないエッジが発見され、矛盾が生じます。

最小頂点カバーを見つけるアルゴリズムは次のとおりです (上記のリンクから)。

1. S0 を M に一致しないすべての頂点で構成するとします。
2. 整数 j ≥ 0 の場合、S(2j+1) をすべての頂点 v の集合とし、v は E \ M のエッジを介して S(2j) の頂点に隣接し、v は以前のどの頂点にも含まれていません。 k < 2j+1 で定義されたセット Sk。そのような頂点がなく、以前に定義された集合 Sk に含まれていない頂点が残っている場合、これらのいずれかを任意に選択し、S(2j+1) をその単一の頂点で構成するようにします。
3. 整数 j ≥ 1 の場合、S(2j) をすべての頂点 u の集合とし、u は M のあるエッジを介して S(2j−1) の頂点に隣接します。S(2j−1) の各 v には、それが一致する頂点 u があることに注意してください。したがって、M は、S(2j-1) の頂点と S(2j) の頂点の間に 1 対 1 の対応を設定します。

奇数のインデックス付きサブセットの和集合が頂点カバーです。