京都大学数理解析研究所

紹 介

　私の研究対象はマッチング問題の一般化である。 マッチング問題は効率的に解ける離散最適化問題の代表例であり， 1960 年代における J. Edmonds によるマッチングの組合せ的アルゴリズムや 多面体的表現は，その後の離散最適化の研究の礎を成してきた。 一方，マッチング問題の妥当な一般化は NP 困難な問題や入り組んだアルゴリズムしか知られていない問題であることが多い。 私はこれまでの研究において， マッチング問題の様々な一般化に対して， 多項式時間で解ける問題クラスにおける組合せ的アルゴリズムの構築を行ってきた。 また， 対象とする 問題 が離散凸性を持つ必要十分条件を示すことにより， 扱った問題クラスの妥当性 を与えてきた。
　論文[1,2,3,4,8] で扱った独立偶因子とは，2001 年に W.H. Cunningham と J.F. Geelen によって提唱された， マッチングとマトロイド交叉の共通の一般化である。 独立偶因子問題は一般には NP 困難であるが， 奇閉路対称と呼ばれるグラフクラスにおいては多項式時間可解である。 特に，重みおよびマトロイド制約のない最も基本的なケースである偶因子問題に対し， 奇閉路対称グラフにおける組合せ的なアルゴリズムが G. Pap (2007) によって設計された。 この Pap のアルゴリズムを重みおよびマトロイド制約のついた問題に拡張し， [1] において重みつき偶因子の組合せ的アルゴリズム， [2] において独立偶因子の組合せ的アルゴリズムを設計した。 それらをさらに統合し，[8] において重みつき独立偶因子の組合せ的アルゴリズムを与えた。 以上のアルゴリズムから，マッチングとマトロイド交叉に対する最大最小定理， 分割定理，多面体的表現の共通の拡張を得た。
　また，偶因子に関する研究のほとんどすべては奇閉路対称グラフにおいて行われてきたが， 論文[3] では 奇閉路対称性の仮定の妥当性を検証した。 具体的には， 偶因子の次数列全体がジャンプシステムという離散凸構造を成すこととグラフの奇閉路対称性が 必要十分の関係にあることを証明した。 さらにその拡張として， 重みつき偶因子がジャンプシステム上の M 凸関数とよばれる離散凸関数を導出することと重みつきグラフの奇閉路対称性が 必要十分の関係にあることを示した。 以上の結果を含む 偶因子に関する研究の最近の進展を[5] にまとめた。
　論文[4,7,9] は，2-因子とハミルトン閉路のギャップを埋める研究である。 論文[4,9] で扱った$C_k$-free 2-因子とは，辺数が k 以下の閉路を含まない 2-因子である。 [4] では，2 部グラフにおける重みつき $C_4$-free 2-因子の 組合せ的アルゴリズムを与えた。 本アルゴリズムは， 辺数 4 の閉路においては辺重みが頂点に誘導されるグラフに対して適用可能である。 また， この辺重みの性質が， 2 部グラフにおいて重みつき $C_4$-free 2-マッチングがジャンプシステム上の M 凸関数を 導出する必要十分条件であることを示した[9]。 論文[9] ではさらに，$C_4$-free 2-マッチングの次数列全体が 一般グラフにおいてもジャンプシステムを成すという Cunningham の予想 (2002) を証明した。 論文[7] では， 2辺連結 3正則グラフにおける辺数3 の辺カットすべてと交わる 2-因子のうち最小重みのものを 求めるアルゴリズムと， 辺数 3 または 4 の辺カットすべてと交わる 2-因子を求めるアルゴリズムを設計した。
　論文[6,10] においては， 有向森の根集合が一般化マトロイドを成すという知見に基づき， マッチング森と双有向森の解析を行った。 マッチング森とは， 1982年に R. Giles によって提唱された マッチングと有向森の共通の一般化である。 [6] では， マッチング森の端点集合がデルタマトロイドを成すことを証明した。 また， Giles の重みつきマッチング森アルゴリズムの単純化および高速化を行った。 [10] では， 最短双有向森問題が付値マトロイド交叉問題の枠組に入ることを 証明した。
　このように，これまでの研究では 多項式時間可解性が知られていた問題， あるいは問題クラスに対し， 新たな組合せ的アルゴリズムの設計および 離散凸性を持つことの証明をしてきた。 今後は， 計算複雑度が未解決の問題に対し離散凸性を持つ条件を見出し， その条件においてアルゴリズムを設計するという方向の研究も行いたい。 例えば， $C_k$-free 2-因子問題については 一般グラフにおける重みなしの $C_4$-free 2-マッチング問題と 重みつき $C_3$-free 2-マッチング問題の計算複雑度が未解決であるが， [9] の結果から前者の問題は 多項式時間可解であることが期待できる。

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. Covering cuts in bridgeless cubic graphs, RIMS Preprint, RIMS-1731 (2011). (with S. Boyd and S. Iwata)
8. A weighted independent even factor algorithm, Math. Program., 132 (2012), 261--276.
9. A proof to Cunningham's conjecture on restricted subgraphs and jump systems, J. Combin. Theory, {\bf B}. (with Y. Kobayashi and J. Szabó)
10. Shortest bibranchings and valuated matroid intersection, Japan J. Indust. Appl. Math., published online.