小特集編集にあたって

編集チームリーダー　武永康彦

　グラフアルゴリズムの研究は，アルゴリズム分野において，初期から現在に至るまで非常に大きな比重を占めてきました．その理由は，グラフにより現実世界の様々な分野における多様な概念が表されることにあります．分かりやすい例を挙げると，道路網，鉄道網などの交通ネットワーク，ソーシャルネットワーク，コンピュータネットワーク，Webページ間のリンク関係などはグラフで表現されます．

　しかし，グラフ上の問題の多くがNP完全と呼ばれる，グラフのサイズに対して指数的な計算時間を必要とするであろう計算困難な問題であることが知られています．そのような問題に対処するため，これまでに様々なアプローチで研究がなされてきました．しかも，近年はソーシャルメディアの発展などにより，グラフ構造を持つビッグデータが増加しており，効率的なグラフアルゴリズムの研究がますます重要になっていくと考えられます．

　本小特集では，グラフアルゴリズムの最先端の研究を幅広く紹介致します．編集にあたっては，この分野で御活躍されている九州大学の来嶋秀治氏にゲストエディターとして御協力頂きました．

　本小特集で扱われている内容の中には，古くからのグラフアルゴリズムのイメージとは異なるものも多く含まれています．まず第1章として，来嶋氏に本小特集を概観する記事を御執筆頂きました．第2章では，実問題への応用も広いグラフのマッチング問題とその一般化について解説を行っています．第3章では，大規模グラフが特定の性質を満たすかどうかを定数時間で判定する手法について解説を行っています．第4章では，グラフの全頂点を一度ずつ通って元に戻る経路が存在するかという問題を扱っています．第5章では，頂点間の距離が近い頂点集合を求める問題を扱っており，緊密な関係にある集団を求めることに相当します．第6章では，二つのグラフが同じ形かどうかを判定するグラフ同形性判定問題についての研究を紹介しています．第7章では，棒材を結合して作られた構造物をグラフとして捉え，その安定性を扱っています．第8章では，ユークリッド空間を一般化した空間上でのアルゴリズムなどを紹介しています．第9章では，条件を満たす低コストのネットワークを設計する問題に対する手法を紹介しています．第10章では，問題の条件を緩和することにより，計算困難な問題を効率的に解く手法を解説しています．第11章では，ある状態から別の状態に遷移可能かという組合せ遷移問題の研究動向を紹介しています．第12章では，大規模なグラフデータから，求められる性質を満たす部分を列挙する手法について解説しています．第13章では，大量のデータを圧縮した形で保持できるデータ構造であるZDDを用いた列挙手法等を紹介しています．

　本小特集により，この分野に関心の深い読者には最先端の研究動向を幅広く知って頂き，この分野に余りなじみのない読者にも興味のある話題を見つけて関心を持って頂ければ幸いです．

　最後に，お忙しい中，本小特集に原稿を御執筆頂いた執筆者の皆様とゲストエディタとして御尽力頂いた来嶋秀治氏をはじめとする編集チームの皆様，本企画を立ち上げて進めて頂いた前編集特別幹事である茨城大学の藤芳明生氏，学会事務局の皆様に深く御礼申し上げます．