所員 -高澤 兼二郎-

名前 高澤 兼二郎 (Takazawa, Kenjiro)
助教
E-Mail takazawa (emailアドレスには@kurims.kyoto-u.ac.jp をつけてください)
研究内容 離散最適化の研究
紹 介
 私の研究対象はマッチング問題の一般化である。 マッチング問題は効率的に解ける離散最適化問題の代表例であり, 1960 年代における J. Edmonds によるマッチングの組合せ的アルゴリズムや 多面体的表現は,その後の離散最適化の研究の礎を成してきた。 一方,マッチング問題の妥当な一般化は NP 困難な問題や入り組んだアルゴリズムしか知られていない問題であることが多い。 私はこれまでの研究において, マッチング問題の様々な一般化に対して, 多項式時間で解ける問題クラスにおける組合せ的アルゴリズムの構築を行ってきた。 また,対象とする問題が離散凸性を持つ必要十分条件を示すことにより, 扱った問題クラスの妥当性を与えてきた。
 論文[1,2,3,5,7]で扱った独立偶因子とは, 2001 年に W.H. Cunningham と J.F. Geelen によって提唱された, マッチングとマトロイド交叉の共通の一般化である。 独立偶因子問題は一般には NP 困難であるが, 奇閉路対称と呼ばれるグラフクラスにおいては多項式時間可解である。 特に,重みおよびマトロイド制約のない最も基本的なケースである偶因子問題に対し, 奇閉路対称グラフにおける組合せ的なアルゴリズムが G. Pap (2007) によって設計された。 この Pap のアルゴリズムを重みおよびマトロイド制約のついた問題に拡張し, [1]において重みつき偶因子の組合せ的アルゴリズム, [2]において独立偶因子の組合せ的アルゴリズムを設計した。 それらをさらに統合し,[7]において重みつき独立偶因子の組合せ的 アルゴリズムを与えた。 以上のアルゴリズムから,マッチングとマトロイド交叉に対する最大最小定理, 分割定理, 多面体的表現の共通の拡張を得た。
 また,偶因子に関する研究のほとんどすべては奇閉路対称グラフにおいて行われてきたが,論文[3]では 奇閉路対称性の仮定の妥当性を検証した。 具体的には, 偶因子の次数列全体がジャンプシステム という離散凸構造を成すこととグラフの奇閉路対称性が 必要十分の関係にあることを証明した。 さらにその拡張として, 重みつき偶因子がジャンプシステム上の M 凸関数とよばれる離散凸関数を導出することと重みつきグラフの奇閉路対称性が 必要十分の関係にあることを示した。 以上の結果を含む 偶因子に関する研究の最近の進展を[5]にまとめた。
 論文[6,9]においては, 有向森の根集合が一般化マトロイドを成すという知見に基づき, マッチング森双有向森の解析を行った。 マッチング森とは, 1982年に R. Giles によって提唱された マッチングと有向森の共通の一般化である。 [6]では, マッチング森の端点集合がデルタマトロイドを成すことを証明した。 また,Giles の重みつきマッチング森アルゴリズムに対し 有向森の一般化マトロイド構造に注目した単純化 および重みつきマッチングへの手法を適用した高速化を行った。 [9]では, 最短双有向森問題が付値マトロイド交叉問題の枠組に入ることを 証明した。
 また,マッチング問題などに対する離散最適化の手法をハミルトン閉路問題,あるいはその緩和問題へ 適用することにも取り組んでいる。 これまでの研究では,$C_k$-free $2$-因子 特定の辺カットと交わる $2$-因子最小 2辺連結部分グラフといった ハミルトン閉路の緩和概念を扱ってきた。 論文[4,8]で扱った $C_k$-free $2$-因子とは,辺数が $k$ 以下の閉路を含まない 2-因子である。 [4]では,2部グラフにおける重みつき $C_4$-free 2-因子問題に対し, 最小費用流問題への手法を適用し 組合せ的アルゴリズムを与えた。 本アルゴリズムは, 辺数4の閉路においては辺重みが頂点に誘導されるグラフに対して適用可能である。 また, この辺重みの性質が, 2部グラフにおいて重みつき $C_4$-free 2-マッチングがジャンプシステム上の M 凸関数を 導出する必要十分条件であることを示した[8]。 論文[8]ではさらに,$C_4$-free 2-マッチングの次数列全体が 一般グラフにおいてもジャンプシステムを成すという Cunningham の予想 (2002) を証明した。 論文[10]では, 2辺連結3正則グラフにおいて辺数3の辺カットすべてと交わる 2-因子のうち最小重みのものを 求めるアルゴリズムと, 辺数3または4の辺カットすべてと交わる 2-因子を求めるアルゴリズムを設計した。 さらに,後者のアルゴリズムを前処理として, 3辺連結3正則グラフにおける最小2辺連結部分グラフの $6/5$ 近似アルゴリズムを設計した。
 このように,これまでの研究では主に, 多項式時間可解性が知られていた問題, あるいは問題クラスに対し, 新たな組合せ的アルゴリズムの設計および 離散凸性を持つことの証明をしてきた。 今後は, 計算複雑度が未解決の問題に対し離散凸性を持つ条件を見出し, その条件においてアルゴリズムを設計するという方向の研究も行いたい。 例えば, $C_k$-free $2$-因子問題については 一般グラフにおける重みなしの $C_4$-free 2-マッチング問題と 重みつき $C_3$-free 2-マッチング問題の計算複雑度が未解決であるが, [8]の結果から前者の問題は 多項式時間可解であることが期待される。 また, 特に巡回セールスマン問題に関連した NP 困難な問題に対し, 離散凸解析などの離散最適化の理論を用いた 高速かつ近似率の良いアルゴリズムの設計にも取り組みたい。
  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. Even factors: algorithms and structure, In: S. Iwata (ed.), Combinatorial Optimization and Discrete Algorithms, RIMS Kôkyôroku Bessatsu, B23 (2010), 233--252.
  6. Optimal matching forests and valuated delta-matroids, Proc. 15th IPCO Conference, Lecture Notes Comput. Sci., 6655 (2011), 404--416.
  7. A weighted independent even factor algorithm, Math. Program., 132 (2012), 261--276.
  8. 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})
  9. Shortest bibranchings and valuated matroid intersection, Japan J. Indust. Appl. Math., 29 (2012), 561--573.
  10. Finding 2-factors closer to TSP tours in cubic graphs, SIAM J. Discrete Math., 27 (2013), 918--939. (with S. Boyd and S. Iwata)