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.

File:Quasi-bipartite.png

This concept was introduced by Rajagopalan and Vazirani {{citation

| contribution = On the bidirected cut relaxation for the metric Steiner tree problem

| title = Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms

| year = 1999

| pages = 742–751

| url = http://portal.acm.org/citation.cfm?id=314909}}. 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{{citation

|first = Romeo |last=Rizzi

|title = On Rajagopalan and Vazirani's 3/2-approximation bound for the Iterated 1-Steiner heuristic

|journal = Inf. Process. Lett.

|volume = 86

|year = 2003

|pages = 335–338

|doi = 10.1016/S0020-0190(03)00210-2

|issue = 6

}}. and a 4/3 approximation algorithm was obtained by Chakrabarty et al.{{citation

| contribution = New Geometry-Inspired Relaxations and Algorithms for the Metric Steiner Tree Problem

| title = Proc. 13th IPCO

| year = 2008

| pages = 344–358

| doi = 10.1007/978-3-540-68891-4_24

| volume = 5035

| series = Lecture Notes in Computer Science

| isbn = 978-3-540-68886-0}}.

The same concept has been used by subsequent authors on the Steiner tree problem, e.g.{{citation

| contribution = Lower Bounds for Approximation Algorithms for the Steiner Tree Problem

| title = Graph-Theoretic Concepts in Computer Science : 27th International Workshop, WG 2001

| publisher = Springer-Verlag, Lecture Notes in Computer Science 2204

| pages = 217–228

| year = 2001

| doi = 10.1007/3-540-45477-2_20

| volume = 2204

| series = Lecture Notes in Computer Science

| isbn = 978-3-540-42707-0}}. Robins and Zelikovsky{{citation

| last1 = Robins|first1= Gabriel|last2= Zelikovsky|first2= Alexander

| contribution = Improved Steiner tree approximation in graphs

| title = Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms

| year = 2000

| pages = 770–779

| url = http://portal.acm.org/citation.cfm?id=338219.338638}}.

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.{{cite book |last1=Goemans |first1=Michel |last2=Olver |first2=Neil |last3=Rothvoss |first3=Thomas |last4=Zenklusen |first4=Rico

|title=Proceedings of the forty-fourth annual ACM symposium on Theory of computing |chapter=Matroids and integrality gaps for hypergraphic steiner tree relaxations |date=2012 |page=1161-1176 |doi=10.1145/2213977.2214081|isbn=9781450312455 |s2cid=13424446 |chapter-url=https://ir.cwi.nl/pub/26962 }} 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.{{citation

| title = Steiner trees in uniformly quasi-bipartite graphs

| journal = Information Processing Letters

| volume = 83

| issue = 4

| year = 2002

| pages = 195–200

| doi = 10.1016/S0020-0190(01)00335-0}}.

References

Category:Graph families

Category:Bipartite graphs