Квазидвудольный граф

Квазидвудольным называется случай задачи Штейнера о минимальном дереве (состоящей из неориентированного графа G и множества R терминальных вершин), в котором нетерминальные вершины графа G образуют независимое множество. Это определение обобщает концепцию двудольного графа — если граф G двудолен и одна из его долей образует множество R, то множество R автоматически является независимым.

Эту концепцию предложили Раджагопалан и Вазирани и использовали её, чтобы дать ( 3 / 2 + ϵ ) {displaystyle (3/2+epsilon )} -аппроксимационный алгоритм для задачи Штейнера в таких графах. Впоследствии Рицци избавился от ϵ {displaystyle epsilon } в данной оценке, а Чакрабарти с соавторами предложили 4/3-аппроксимационный алгоритм. В дальнейшем ту же концепцию использовали другие авторы, например, Робинс и Зеликовски предложили аппроксимационный алгоритм для задачи Штейнера, который на квазидвудольных графах имеет аппроксимационный коэффициент 1,28. Алгоритм Робинса и Зеликовски работает за время O ( m n 2 ) {displaystyle O(mn^{2})} , где m и n — количества терминальных и нетерминальных вершин в графе соответственно. В дальнейшем, Грёпль с соавторами предложили 1,217-аппроксимационный алгоритм для особого случая однородных квазидвудольных случаев.