次数上下界制約付きグラフ向き付けにおけるペナルティ最小化

概要

論文の詳細を見る
無向グラフG=(V,E)が与えられたとき,ある制約を満たすように各辺に向き付けを与えた有向グラフG^^→=(V,Λ(E))を求める問題をグラフ向き付け問題という.Λ(E)は辺{u,v}∈Eの向き付け割当集合を表す.本稿では次数制約の下でのグラフ向き付け問題を扱う:各頂点vについて正整数a_vとb_v(a_v≦b_v)が指定されたとき,できるだけ多くの頂点vについてa_v≦|{(v,u)∈Λ(E)}|≦b_vとなるGの向き付けを求める.本稿では,Σ_<v∈V>c_vを最小化するグラフ向き付けを求める問題を考える.ここで,c_vは次数制約を満たさない頂点vに対するペナルティを表している.本稿では以下を示す.(i)任意の凸なペナルティ関数(線形関数を含む)を考えたときの次数制約の下でのグラフ向き付け問題はO(m^<1.5>min{log(nC),Δ^<0.5>})時間で解くことができる.ここで,n=|V|およびm=|E|であり,ΔとCはそれぞれ最大次数とペナルティ関数の最大値である.(ii)一方,ステップ関数(すなわち凹関数)の場合にはAPX困難である.(iii)木の場合には,任意のペナルティ関数についてO(n logΔ)時間で解を求めることができ,ペナルティ関数が凸の場合には線形時間で解を求めることができる.
2011-12-09