PPHに用いられるGraph realization problemとは

• 参考　URL　Graph realization
• 定義
  
  • Graph realization problem: "Given subsets P1,..Pn of {0,..,m-1}, find a tree T=(V,E) with E={0,..,m-1} such that every Pi is a path in T, or determine that no such tree exists. "
• 日本語訳(一部意訳)
  
  • 0からm-1までラベル付けされた辺(edge)の集合Eが作る木(tree)Tを作成せよ、もしくはそのような木が存在しないことを示せ。ただし。このTは次の条件を持つ。Tには、n個のパスP1,P2,..,Pnを含む。今、それぞれのパスは辺の集合Eの要素の部分集合の順列である。
• 例
  
  • 5本の辺がある
  • パスとして、３つのパスP1,P2,P3がある
    
    • P1={0,1}
    • P2={0,2,3}
    • P3={1,2,3,4}
• 拡張問題としては次のような問題がある
  
  • Further, determine if there is only one such T, and if there is more than one, characteriza the relationship between the realizing trees.
  • 日本語：さらに、そのような木が存在する場合、そのような木がただ１つ存在するのか、否か、もし、複数存在するのであれば、その複数の木の間の関係はどのような関係であるか
• この問題には数学上の解法が示されている
• 実用上の課題は、その解法をいかにlinearに近い処理回数で解くか、である