離散最適化に対する固定パラメータアルゴリズムの深化：多項式時間FPTと実用化

点击翻译按钮获取中文摘要

本研究は，理論計算機科学における計算複雑さおよびアルゴリズム理論の分野で急速な進展を遂げているパラメータ化計算という枠組みのもとで，離散最適化に対する率的なアルゴリズムの設計技法として確立しつつある固定パラメータアルゴリズム理論を扱っている．その理論がもつ，何らかの特徴をもつ実データに対してアルゴリズムを高速に動作させるという理念に鑑み，理論的な成果を挙げると同時に固定パラメータアルゴリズム研究を実用化の段階へ推し進めることを目的とする．本研究は，当初設定した研究期間を経過したが，コロナ感染症による進捗の遅れから研究機関を再延長した．６年度目である令和４年度は，前年度までの方針を踏襲し，理論的な研究を継続するとともに実用的な方向への挑戦を推し進めた．具体的には，まずはじめに理論面からは，Double-Threshold Graph と命名したグラフの認識問題に対して多項式時間アルゴリズムを設計し公表していたが，これを雑誌論文とした．またあらたにグラフ描画に関する重要問題を考察し，それに対する固定パラメータアルゴリズムの開発に着手した．実用的な方向では，ネットワーク解析分野で頻出するネットワーク中心性を厳密に計算する問題を継続して扱い，なかでも最も重要である頂点媒介中心性に対するアルゴリズムの実装の高速化を試みている．また，固定パラメータアルゴリズム分野で基本的な問題の一つであるグラフ燃焼問題に対する固定パラメータアルゴリズムに関する実証実験も継続し，実ネットワークを入力としたときに有効となるカーネル化や有界探索木などの手法を検証している．