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

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

Эта концепция была введена Раджагопаланом и Вазирани ^[1] , которые использовали ее для предоставления алгоритма приближения (3/2 + ε) для задачи дерева Штейнера для таких случаев. Впоследствии фактор ε был удален Рицци ^{[2] , а} алгоритм приближения 4/3 был получен Чакрабарти и др. ^[3] Та же концепция использовалась последующими авторами для задачи дерева Штейнера, например ^[4] Робинс и Зеликовский ^[5] предложили алгоритм приближения для задачи дерева Штейнера, который на квазидвудольных графах имеет коэффициент приближения 1,28. Сложность алгоритма Робинса и Зеликовского составляет O( m n ² ) , где m и n — это количество терминалов и нетерминалов в графе соответственно. В 2012 году Гоеманс и др. ^[6] дал алгоритм с 73/60 ≈ 1,217-приближением для задачи дерева Штейнера на квазидвудольных графах; алгоритм, достигающий того же коэффициента приближения, был ранее известен для особого случая квазидвудольных графов с ребрами единичной стоимости. ^[7]