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

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

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