Quasi-bipartite graph

Content sourced from Wikipedia, licensed under CC BY-SA 3.0.

Quasi-bipartite graphs are a special setup for the Steiner tree problem. You have a graph G and a set R of terminal vertices that must all connect to each other. The non-terminal vertices form an independent set, meaning no two non-terminals are connected by an edge; every edge touches at least one terminal. This idea generalizes bipartite graphs: if G is bipartite and R is one side of the split, then R is automatically independent.

The concept was introduced by Rajagopalan and Vazirani, who showed a (3/2 + ε) approximation algorithm for Steiner tree on quasi-bipartite graphs. The ε term was later removed by Rizzi, and Chakrabarty et al. achieved a 4/3-approximation. Robins and Zelikovsky also studied this setup and produced an algorithm with about a 1.28 approximation factor, with running time O(m n^2) (m is the number of terminals and n the number of non-terminals).

In 2012, Goemans and colleagues gave a 73/60 ≈ 1.217-approximation for Steiner tree on quasi-bipartite graphs. The same approximation factor was already known for the special case of unit-cost edges.