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.

The first graph has non-terminal points which are directly connected, and is therefore non-quasi-bipartite. The second has no non-terminal points which are directly connected, and is therefore quasi-bipartite.

This concept was introduced by Rajagopalan and Vazirani ^[1] 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^[2] and a 4/3 approximation algorithm was obtained by Chakrabarty et al.^[3] The same concept has been used by subsequent authors on the Steiner tree problem, e.g.^[4] Robins and Zelikovsky^[5] 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.^[6] 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.^[7]