In the

mathematical Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

field of

graph theory In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, an instance of the

Steiner tree problem In combinatorial mathematics, the Steiner tree problem, or minimum Steiner tree problem, named after Jakob Steiner, is an umbrella term for a class of problems in combinatorial optimization. While Steiner tree problems may be formulated in a ...

(consisting of an

undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...

''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 In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V ar ...

: 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 In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned solu ...

for the Steiner tree problem on such instances. Subsequently, the ε factor was removed by Rizzi and a 4/3

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

for Steiner tree problem which on quasi-bipartite graphs has

approximation ratio An approximation is anything that is intentionally similar but not exactly equal to something else. Etymology and usage The word ''approximation'' is derived from Latin ''approximatus'', from ''proximus'' meaning ''very near'' and the prefix '' ...

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..

References

{{DEFAULTSORT:Quasi-Bipartite Graph Graph families Bipartite graphs