Quasi-bipartite graph

In the mathematical field of graph theory, an instance of the Steiner tree problem (consisting of an undirected graph G and a set R of terminal vertices that must be connected to each other) is said to be quasi-bipartite if the non-terminal vertices in G form an independent set, i.e. if every edge is incident on at least one terminal. This generalizes the concept of a bipartite graph: if G is bipartite, and R is the set of vertices on one side of the bipartition, the set R is automatically independent. This concept was introduced by Rajagopalan and Vazirani who used it to provide a (3/2 + ε) approximation algorithm for the Steiner tree problem on such instances. Subsequently, the ε factor was removed by Rizzi and a 4/3 approximation algorithm was obtained by Chakrabarty et al. The same concept has been used by subsequent authors on the Steiner tree problem, e.g. Robins and Zelikovsky proposed an approximation algorithm for Steiner tree problem which on quasi-bipartite graphs has approximation ratio 1.28. The complexity of Robins and Zelikovsky's algorithm is O(m n²), where m and n are the numbers of terminals and non-terminals in the graph, respectively. In 2012, Goemans et al. gave a 73/60 ≈ 1.217-approximation algorithm for the Steiner tree problem on quasi-bipartite graphs; an algorithm achieving the same approximation factor was previously known for the special case of quasi-bipartite graphs with unit cost edges.