単純なグラフ G =(V; E) を考えます。よく知られているパス カバー問題 ( https://en.wikipedia.org/wiki/Path_cover ) は、ハミルトニアン パス問題が NP 完全であるすべてのグラフ クラス (平面グラフ、2 部グラフ、および弦グラフを含む) で NP 完全です。多くの多項式アルゴリズムが、この問題が多項式である特別なグラフ クラスの文献で提案されていますが、2 部グラフ (または平面グラフや弦グラフ) の最小の頂点分離パス カバーを見つけるための正確な方法は見つかりませんでした。 、特に分岐限定アルゴリズム。
この問題が NP 困難であるグラフ クラス (2 部グラフ、平面グラフ、弦グラフ) でのパス カバー問題の正確な方法、特に分岐限定アルゴリズムを知っていますか?
前もって感謝します。