WADS 2日目
今日もいろいろと面白い話が聞けました．
The Lens of Computation: How the Algorithmic Point of View is Changing the Sciences
Christos Papadimitriou
招待講演2件目．最近Papadimitriouはこの話しかしていない気もするけど，それほど普及に努めているということなんだろう．いわゆる「計算世界観」についての話で，京都賞のときにKarpが話をしたものよりもしっかりしている．しかし，私自身とPapadimitriouのペースの波長が合わないので，いまいち理解できなかった．生物における性の役割の話について計算世界観から切り込んだ最新の研究の話も紹介された．
Orientation-Constrained Rectangular Layouts
David Eppstein, Elena Mumford
正方形を長方形にうまく分割した図形をrectangular layoutと呼ぶことにして，その双対グラフを考える．双対グラフから元のrectangular layoutが一意に復元できるかというとそうではないが，双対グラフ(をちょっと拡大したグラフ)の各辺に「向き」の情報があると一意に復元できる．ただし，適当に向き情報を与えても対応するrectangular layoutがあるとは限らない．この論文では双対グラフの辺の一部に向き情報が与えられたときに対応するrectangular layoutがあるかどうか判定し，ある場合にはそれを出力するアルゴリズムを与えている．Rectangular layout全体の集合上に定義されたある束が分配束になり (Fusy 2009?)，それにBirkoffの表現定理を適用するという枠組はEppstein, Mumford, Speckmann, Verbeek (SoCG 2009) と同じである．
Drawing Graphs with Right Angle Crossings
Walter Didimo, Peter Eades, Giuseppe Liotta
面白い．
グラフ描画の話で，辺交差が直角であれば見た目が悪いわけではない，という観察結果から，そのような描画可能性を探求している．直線描画で辺交差を直角にできるグラフの辺数が高々4n-10になり，それがタイトであることや，任意のグラフは関節を2つ持つ折れ線で辺を表現した描画で辺交差を直角にできる，とか．この話を聞いただけで研究テーマがどんどん浮かんできた．楽しい．
Dynamic Graph Clustering Using Minimum-Cut Trees
Robert Gorke, Tanja Hartmann, Dorothea Wagner
Flake, Tarjan, Tsioutsiouliklis (2004) の提案したGomory-Hu木を基にしたグラフ・クラスタリングのアルゴリズムをdynamizeする．実は，それをSahaとMitra (ICDM 2007) は行っているが，彼らのアルゴリズムは間違っている (ということを発見したのもこの研究の成果)．そこでこの研究では正しいアルゴリズムを提案して，実験もしている．
Straight-Line Rectangular Drawings of Clustered Graphs
Patrizio Angelini, Fabrizio Frati, Michael Kaufmann
いわゆるc-planar graphの各クラスタを長方形にして全体の直線的平面描画が得られるか，という問題をEades, Feng, Lin, Nagamochi (2006) は提案したが，この研究ではそれを肯定的に解決した．
On Making Directed Graphs Transitive
Mathias Weller, Christian Komusiewicz, Rolf Niedermeier, Johannes Uhlmann
与えられた有向グラフを推移的にするために追加・削除する辺の個数を最小化する問題を考える．これはBocker, Briesemeister, Klau (APBC 2009) が考えた問題で，製薬に応用があるらしい．彼らの結果はこの問題に対するNP完全性と固定パラメータ・アルゴリズムであるが，NP完全性の証明が載っていないらしい．そこでこの研究ではNP完全性の証明を与え，さらに固定パラメータ・アルゴリズムも改善している．内容は分かりやすかった．
The Simultaneous Representation Problem for Chordal, Comparability and Permutation Graphs
Krishnam Raju Jampani, Anna Lubiw
例えば弦グラフが2つ与えられて，それらが一部の頂点を共有しているとする．このとき，2つのグラフの頂点の間に辺を追加して (しかし共有頂点には辺を追加してはいけない)，全体を弦グラフにできるか，という問題を考える．これが多項式時間で解ける，というのがこの論文の結果の1つ．同じような結果を比較可能グラフと置換グラフに対しても与えている．また，最後のまとめのところで，区間グラフに対しても同じ結果が得られているという報告もあった．
Plane Graphs with Parity Constraints
Oswin Aichholzer, Thomas Hackl, Michael Hoffmann, Alexander Pilz, Guenter Rote, Bettina Speckmann, Birgit Vogtenhuber
平面上のn点集合と，その各点に偶奇のラベルが与えられたとき，その上の三角形分割で頂点の次数ができるかぎり与えられた偶奇ラベルと合うようにしたい，という問題を考える．この論文では常におよそ2n/3個の点のラベルを合わせることができ，だいたい107n/108個よりたくさん合わせられない場合がある，ということを示している．
An Improved Algorithm for the General Satisfiability Problem
Jianer Chen, Yang Liu
普通のSATに対する指数時間アルゴリズムで，論理式の長さLに対してどれだけ速くできるか，という話．既存の最速が1.0663^Lぐらい (Wahlstrom ESA2005) だったのに対して，ここではそれを1.0652^Lぐらいに改善している．やってることはいわゆるmeasure and conquerで，個人的にはあんまり面白さを感じなかった．
Streaming Embeddings with Slack
Christiane Lammersen, Anastasios Sidiropoulos, Christian Sohler
ストリーミング計算の話で，ユークリッド空間内の点がどんどんやってきてもすべてを覚えられないので，その中のいくつかの対の距離だけは近似的に記憶しておけるアルゴリズムを提案している．基本的な技法はwell-separated pair decompositionの利用で，まずその定義をちょっと拡張する．あとは拡張した定義に従って普通のwell-separated pair decompositionを構成するような分割型アルゴリズムのようなものを実現する．ストリームからのランダム・サンプリングが必要になるので，そこはreservoir samplingを用いる．
