Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization

Jiong Guo, Jens Gramm, Falk Huffner, Rolf Niedermeier and Sebastian Wernicke
Journal of Computer and System Sciences
Volume 72, Issue 8 , December 2006, Pages 1386-1396
http://dx.doi.org/10.1016/j.jcss.2006.02.001

WADS2005の論文．
「Iterative compression」(反復圧縮) という技法を用いて固定パラメータアルゴリズムを設計する例．
反復圧縮はgraph bipartization問題に対してReed, Smith, and Vetta (2004) が開発した技法で，この名前を付けたのは確かDaniel Marxである．
このJenaのグループの論文は読みやすくてよい．