Are there any good digraph width measures?

Robert Ganian, Petr Hliněný, Joachim Kneis, Daniel Meister, Jan Obdržálek, Peter Rossmanith, Somnath Sikdar
http://arxiv.org/abs/1004.1485

グラフの木幅 (treewidth) の果たす役割はグラフ理論，グラフ・アルゴリズムの世界ではとても大きいが，その有向グラフ版をどうすればよいか，ということに対して，うまい一般化がまだできていないという現状がある．
この論文 (の結果の1つ) は，そのような一般化が持っていて欲しい性質を満たすときには，結局向きを無視したグラフの木幅と同等なものしか一般化として現れない，ということを示している．これは真の一般化がうまくできなそうだということを示す否定的な結果と捉えることができる．