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

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

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

Литература

• Clemens Gröpl, Stefan Hougardy, Till Nierhoff, Hans Jürgen Prömel. Steiner trees in uniformly quasi-bipartite graphs // Information Processing Letters. — 2002. — Т. 83, вып. 4. — С. 195–200. — doi:10.1016/S0020-0190(01)00335-0.
• Sridhar Rajagopalan, Vijay V. Vazirani. On the bidirected cut relaxation for the metric Steiner tree problem // Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms. — 1999. — С. 742–751.
• Romeo Rizzi. On Rajagopalan and Vazirani's 3/2-approximation bound for the Iterated 1-Steiner heuristic // Inf. Process. Lett.. — 2003. — Т. 86, вып. 6. — С. 335–338. — doi:10.1016/S0020-0190(03)00210-2.
• Deeparnab Chakrabarty, Nikhil R. Devanur, Vijay V. Vazirani. New Geometry-Inspired Relaxations and Algorithms for the Metric Steiner Tree Problem // Proc. 13th IPCO. — 2008. — Т. 5035. — С. 344–358. — (Lecture Notes in Computer Science). — ISBN 978-3-540-68886-0. — doi:10.1007/978-3-540-68891-4_24.
• Clemens Gröpl, Stefan Hougardy, Till Nierhoff, Hans Jürgen Prömel. Lower Bounds for Approximation Algorithms for the Steiner Tree Problem // Graph-Theoretic Concepts in Computer Science : 27th International Workshop, WG 2001. — Springer-Verlag, 2001. — Т. 2204. — С. 217–228. — (Lecture Notes in Computer Science). — ISBN 978-3-540-42707-0. — doi:10.1007/3-540-45477-2_20.
• Gabriel Robins, Alexander Zelikovsky. Improved Steiner tree approximation in graphs // Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms. — 2000. — С. 770–779.