所員 -高澤 兼二郎-

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