抄録

◎福田　俊（東北大）・Bernd Gärtner（ETH Zürich）・森山園子Gärtner（日大）・宮田洋行（東北大）・Lorenz Klaus（NII）

線形相補性問題(LCP)は線形計画問題、２次計画問題、双行列ゲームといった問題の統一的枠組みを与える重要な問題として研究されてきた。一般にLCPはNP困難であるが、LCPに現れる行列をP行列に限定した場合、解が一意に定まることが知られており、行列を限定した場合の計算複雑性について研究が進められている。先行研究としてP行列の部分クラスとして存在するK行列では、LCPを有向グラフの向き付けとしてモデル化して解くピボットアルゴリズムが線形ステップで終了することが知られている。本論文では、そのような良い性質を持つ有向グラフの向き付けを列挙した結果と、その性質がK行列でない行列にも現れることを示す。