Optimal broadcast domination in polynomial time

Pinar Heggernes and Daniel Lokshtanov
Discrete Mathematics
Volume 306, Issue 24 , 28 December 2006, Pages 3267-3280
http://dx.doi.org/10.1016/j.disc.2006.06.013

WG2005で聞いた話．
グラフのbroadcast dominationはErwin (2004) が提案した概念で，次のように定義される．
無向グラフG=(V,E)のbroadcast dominationとは各頂点vへの0以上の整数の割当f(v)で，
全ての頂点uに対して，ある頂点wが存在して，uとwの間の距離がf(w)以下であるようなもののことである．
そのとき，optimal broadcast dominationとはf(v)を全ての頂点vに関して足し合わせたものを最小にするbroadcast dominationである．
割り当てる整数f(v)が0か1しか取れないものが通常のdomination問題である．
この論文では，optimal broadcast dominationを見つけるO(n^6)時間アルゴリズムを与えている (nはグラフの頂点数)．

アルゴリズムが用いている面白い性質は，optimal broadcast dominationで，各頂点がちょうど1つの頂点からしか支配されないようなものが存在するという結果 (Dunbar, Erwin, Haynes, Hedetniemi, and Hedetniemi 2006) である．
このとき，支配領域の隣接関係を別のグラフで表わしたとき，それがパスかサイクル(のdisjoint union)になるものが存在することも分かり，それを用いてアルゴリズムが設計される．技法が特殊すぎるけどなかなか面白い．

応用上のことを考えると，f(v)の和をコストとするのではなくて，f(v)の2乗の和をコストとした方が自然な気もするけれど，コストをそう変えた場合に多項式時間で解けるかどうかは分かってないようである．
これは来年のGWOP問題候補．