所員 -高澤 兼二郎-

名前 高澤 兼二郎 (Takazawa, Kenjiro)
助教
E-Mail takazawa (emailアドレスには@kurims.kyoto-u.ac.jp をつけてください)
研究内容 離散最適化の研究
紹 介
 私の主な研究対象はマッチング問題の一般化である。 マッチング問題は効率的に解ける離散最適化問題の代表例であり, 1960 年代における J. Edmonds によるマッチングの組合せ的アルゴリズムや 多面体的表現は,その後の離散最適化の研究の礎を成してきた。 一方,マッチング問題の妥当な一般化は NP 困難な問題や入り組んだアルゴリズムしか知られていない問題であることが多い。 私のこれまでの研究では, 問題が離散凸性をもつ条件に注目することにより 多項式時間下界であるクラスを解明し, 組合せ最適化の古典的なアルゴリズムの拡張を与えてきた。
 論文[1,2,3,5] で扱った独立偶因子とは, マトロイドの共通独立集合とマッチングとの共通の一般化である。 マトロイドの共通独立集合もまた, 多項式時間可解である離散最適化問題である。 その記述力の高さから多くの最適化問題を含む一方で, マッチングはマトロイドの共通独立集合では記述できないことが知られている。 これらの二つの問題の共通の一般化である独立偶因子問題には, 例えば点素パス問題や Tutte 行列の小行列の階数計算などが含まれる。
 独立偶因子問題は NP 困難であるが, 奇閉路対称とよばれるグラフクラスにおいては多項式時間可解である。 論文[1,2,5] においては, 奇閉路対称グラフにおける重み付き独立偶因子の組合せ的アルゴリズムを与えた。 本アルゴリズムはマッチングおよびマトロイドの共通独立集合に対する古典的なアルゴリズムの共通の拡張であり, マッチングとマトロイドの共通独立集合に対する最大最小定理,分割定理, 多面体的表現の共通の拡張を導いた。 また, 論文[3] では 偶因子がジャンプシステムおよびジャンプシステム上の M 凸関数 という離散凸構造を導出することとグラフの奇閉路対称性が 必要十分の関係にあることを証明した。 本結果から, 偶因子問題に対する厳密アルゴリズムを考えるにあたっては 奇閉路対称グラフを扱うことが自然であると示唆される。
 論文[7,9] ではそれぞれ, 双有向森問題および マッチング森問題の 離散凸性を証明した。 これらの問題に対しては多項式時間アルゴリズムが既に設計されており, その多項式時間可解性は 完全双対整数性をもつ線形計画表現に起因すると理解されてきた。 本研究ではこれらの問題の扱いやすさは 離散凸性に起因するという, 多項式時間可解性に対する新たな理由付けを与えた。 さらに, 各々の問題に対し, その離散凸性を活かしたアルゴリズムを設計した。
 また,マッチング理論などの離散最適化の理論を, 主に巡回セールスマン問題などの応用上重要な問題へ適用する研究も行っている。 論文[4,6,8,10] では, ハミルトン閉路と $2$-因子の中間に位置する 様々な制約付き $2$-因子の離散凸性の分析や アルゴリズム設計を行った。
 論文[4,6,10] で扱った $C_4$-free $2$-因子とは, 辺数が $4$ 以下の閉路を含まない 2-因子である。 論文[4] では, 2 部グラフにおける重み付き $C_4$-free 2-因子問題に対し 最小費用流問題への手法を用いた 主双対アルゴリズムを与えた。 本アルゴリズムは, 辺数 4 の閉路において辺重みが頂点に誘導されるグラフに対して適用可能である。 また, 論文[6] では, 上記の辺重みの性質が 2部グラフにおいて重み付き $C_4$-free 2-マッチングがジャンプシステム上の M 凸関数を 導出する必要十分条件であることを証明し, この辺重みの仮定の妥当性を示した。 論文[6] ではさらに, $C_4$-free 2-マッチングの次数列全体が 一般グラフにおいてもジャンプシステムを成すという Cunningham の予想を証明した。 一般グラフにおける $C_4$-free $2$-マッチング問題の計算複雑度は未解決であるが, 本結果により多項式時間可解であることが予想される。 論文[10] では, 2部グラフにおける $C_4$-free $2$-マッチングに対し, Dulmage-Mendelsohn 分解および Edmonds-Gallai 分解に対応する分解定理を与えた。
 論文[8] では, 辺数~$3$ の辺カットすべてと交わる $2$-因子 ($\{3\}$-カット $2$-因子) と 辺数~$3$ または $4$ の辺カットすべてと交わる $2$-因子 ($\{3,4\}$-カット $2$-因子) を扱った。 ハミルトン閉路をすべての辺カットと交わる $2$-因子と捉えることにより, これらもまた巡回セールスマン問題の緩和問題となる。 論文[8] では, 2辺連結 3正則グラフにおける 最小重み $\{3\}$-カット $2$-因子アルゴリズム, および, $\{3,4\}$-カット $2$-因子アルゴリズムを設計した。 さらに, 後者のアルゴリズムを前処理として, やはり巡回セールスマン問題の緩和問題である 最小 $2$~辺連結部分グラフ問題に対し, 3辺連結 3正則グラフにおける $6/5$ 近似アルゴリズムを設計した。
 今後の研究においては, これまでと同様に マッチング理論を 離散凸解析などの理論と関連させながら 深化させていくとともに, その中で得られた 新たな理論を応用上重要な問題へ適用することも行っていきたい。 例えば, 上記の様々な制約付き $2$-マッチング, $2$-因子を初期解とする, 巡回セールスマン問題に対する新たな近似アルゴリズムの設計などが考えられる。
  1. A weighted even factor algorithm, Math. Program., 115 (2008), 223-237.
  2. The independent even factor problem, SIAM J. Discrete Math., 22 (2008), 1411-1427. (with S. Iwata)
  3. Even factors, jump systems, and discrete convexity, J. Combin. Theory, B99 (2009), 139-161. (with Y. Kobayashi)
  4. A weighted K_{t,t}-free t-factor algorithm for bipartite graphs, Math. Oper. Res., 34 (2009), 351-362.
  5. A weighted independent even factor algorithm, Math. Program., 132 (2012), 261--276.
  6. A proof of Cunningham's conjecture on restricted subgraphs and jump systems}, J. Combin. Theory, B102 (2012), 948--966. (with Y. Kobayashi and J. Szab\'{o})
  7. Shortest bibranchings and valuated matroid intersection, Japan J. Indust. Appl. Math., 29 (2012), 561--573.
  8. Finding 2-factors closer to TSP tours in cubic graphs, SIAM J. Discrete Math., 27 (2013), 918--939. (with S. Boyd and S. Iwata)
  9. Optimal matching forests and valuated delta-matroids}, SIAM J. Discrete Math., 28 (2014), 445--467.
  10. Decomposition theorems for square-free $2$-matchings in bipartite graphs}, Proc. 41st Int. Workshop on Graph-Theoretic Concepts in Computer Science, Lecture Notes in Comput. Sci., to appear.