java - 非比較関係が LinkedHashMap として与えられた場合の最大アンチチェーンの計算

Question

特定のposetの最大アンチチェーンを計算しようとしています。次のメソッドを作成しました。

public boolean isIncomparable(Node a,Node b)
{
    if(isReachable(a,b)||isReachable(b,a))
         return false;
    return true;
}

aこれは、2 つのノードが比較できない場合 (つまり、 fromにb も frombにもパスがない場合) にのみ true を返しますa。

LinkedHashMap を定義しました

LinkedHashMap<Node,ArrayList<Node>> map=new LinkedHashMap<Node,ArrayList<Node>>();

これは、すべてのノード N をその比類のない要素にマップしますIncomp(N)。

for(int i=0;i<nodes.size();i++)
{
   Node a=nodes.get(i);
   ArrayList<Node> tmp=new ArrayList<Node>();
   for(int j=i+1;j<nodes.size();j++)
   {
      Node b=nodes.get(j);
      if(isIncomparable(a,b))
           tmp.add(b)
   }
   map.put(a,tmp);
} 

例: 要素が {A,B,C,D} で、A>B、A>C、D>C の関係があるとします。

Incomp(A)={D}
Incomp(B)={C,D}
Incomp(C)={}
Incomp(D)={}

重複は許可されていないことに注意してください (つまりIncomp(C)={B}、(B,C) が含まれIncomp(B)ているため、繰り返す必要はありません)。

私はここで立ち往生しています。要素間の不一致をチェックIncomp(N)してから、最大アンチチェーンとして最大サイズのキーを取得する必要がありますか? つまり、この設定で最大のアンチチェーンを見つける方法は?

これは非効率になるため、サイズ k のすべてのサブセットを生成することはできません。