未解決問題集

今後の班会議の題材になればと、この度、皆様から未解決問題を お寄せ頂けるページを設けました。 世紀の難問から、ちょっと気になる問題までどしどしお寄せ下さい。 どうモデル化したらいいの？という話も歓迎いたします。

問題の名前、説明、背景、出題者名を梅谷(umetani＠?????.kyoto-u.ac.jp) までメイルにてお出し下さい。 （テキストファイルでお送り、願えます。上・下付き添字、ギリシャ文字 程度は対応できますので、その場合latex風にお書き下さい。） 掲載された問題に対するコメント等は直接出題者にお尋ね下さい。

Ｑ１：ハイパーグラフ３分割問題 （出題者：永持　仁）

与えられたハイパーグラフからハイパー辺を取り除き、連結成分を３つ以 上にする。このとき、取り除くべきハイパー辺の数を最小にせよ。

説明：この問題はNP-困難か？　連結成分を２つ以上にするのであれば、 フロー問題に帰着できる。グラフの場合は、連結成分をk個以上にする 最小分割はkを固定すれば多項式時間で解けるが、kを変数とすると NP-困難。

Ｑ２：局所２点連結化問題 （出題者：永持　仁）

単純無向グラフG=(V,E)と いくつかの点対の集合P={(u₁,v₁),(u₂,v₂),...,(u_p,v_p)}が 与えられたとき、どの点対u_i,v_i間の点連結度も２以上になるように、 Gに最小本数の辺を加えたい。

説明：この問題はNP-困難か？ Pがクリークを与える場合には 多項式時間で解けることが知られている(T.-s. Hsu and M.Y.Kao, 1996)。 辺連結度版は多項式時間で解ける。

Ｑ３：最長幾何学的巡回路問題 （出題者：伊藤　大雄）

平面上のn点を入力とし、そのn$点全てを丁度一回ずつ通る閉路で長さ 最長のものを求める問題。点間の距離はユークリッド距離で与えられる。

説明：「最短」幾何学的巡回路問題ならば言うまでも無くNP困難。この問 題もどう見てもNP困難ですが、私の調べた範囲では証明されている文献は ありませんでした。定義は単純で誰でも思いつきそうなので、どこかでや られていても不思議はありませんが、もしかしたら応用があまり無いので やられていないのかもしれません。ユークリッド距離の場合は最短と最長 とは振るまいがかなり違うので、最短幾何学的巡回路問題のNP困難性の証 明からは簡単にもってこれないと思います。

参照：Q3 の maximum TSP ですが，これについては今年のSODAでも発表があり, 過去にいろんな結果が得られています．

• 2点間の距離が L_d 距離 (d = 1, 2, ..., ∞) の場合, PTAS が存在する．
• 特に, L_1 距離の場合は線形時間で求められる．
• L_d 距離の場合, d >= 3 ならば NP困難．
• L_2 距離(平面上)の場合は分かっていない．

詳しくは

S. P. Fekete,

"Simplicity and Hardness of the Maximum Traveling Salesman Problem under Geometric Distances,"

Proceeding of the tenth annual ACM-SIAM symposium on discrete algorithms (1999).

を参照ください．(塩浦 昭義 上智大学)