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 to R is automatically independent.

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 n2), where m and n are the numbers of terminals and non-terminals in the graph, respectively. Furthermore, Gröpl et al.[6] gave a 1.217-approximation algorithm for the special case of uniformly quasi-bipartite instances.

References

  1. ↑ Rajagopalan, Sridhar; Vazirani, Vijay V. (1999), "On the bidirected cut relaxation for the metric Steiner tree problem", Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 742–751.
  2. ↑ Rizzi, Romeo (2003), "On Rajagopalan and Vazirani's 3/2-approximation bound for the Iterated 1-Steiner heuristic", Inf. Process. Lett. 86 (6): 335–338, doi:10.1016/S0020-0190(03)00210-2.
  3. ↑ Chakrabarty, Deeparnab; Devanur, Nikhil R.; Vazirani, Vijay V. (2008), "New Geometry-Inspired Relaxations and Algorithms for the Metric Steiner Tree Problem", Proc. 13th IPCO, Lecture Notes in Computer Science 5035, pp. 344–358, doi:10.1007/978-3-540-68891-4_24, ISBN 978-3-540-68886-0.
  4. ↑ Gröpl, Clemens; Hougardy, Stefan; Nierhoff, Till; Prömel, Hans Jürgen (2001), "Lower Bounds for Approximation Algorithms for the Steiner Tree Problem", Graph-Theoretic Concepts in Computer Science : 27th International Workshop, WG 2001, Lecture Notes in Computer Science 2204, Springer-Verlag, Lecture Notes in Computer Science 2204, pp. 217–228, doi:10.1007/3-540-45477-2_20, ISBN 978-3-540-42707-0.
  5. ↑ Robins, Gabriel; Zelikovsky, Alexander (2000), "Improved Steiner tree approximation in graphs", Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 770–779.
  6. ↑ Gröpl, Clemens; Hougardy, Stefan; Nierhoff, Till; Prömel, Hans Jürgen (2002), "Steiner trees in uniformly quasi-bipartite graphs", Information Processing Letters 83 (4): 195–200, doi:10.1016/S0020-0190(01)00335-0.