Grafo cuasi bipartito

En el campo matemático de la teoría de grafos , una instancia del problema del árbol de Steiner (que consiste en un grafo no dirigido G y un conjunto R de vértices terminales que deben estar conectados entre sí) se denomina cuasi-bipartita si los vértices no terminales de G forman un conjunto independiente , es decir, si cada arista incide en al menos un terminal. Esto generaliza el concepto de grafo bipartito : si G es bipartito y R es el conjunto de vértices de un lado de la bipartición, el conjunto R es automáticamente independiente.

Este concepto fue introducido por Rajagopalan y Vazirani ^{[ 1 ]} quienes lo utilizaron para proporcionar un algoritmo de aproximación (3/2 + ε) para el problema del árbol de Steiner en tales instancias. Posteriormente, el factor ε fue eliminado por Rizzi ^{[ 2 ]} y Chakrabarty et al. ^{[ 3 ]} obtuvieron un algoritmo de aproximación 4/3 El mismo concepto ha sido utilizado por autores posteriores en el problema del árbol de Steiner, por ejemplo ^{[ 4 ]} Robins y Zelikovsky ^{[ 5 ]} propusieron un algoritmo de aproximación para el problema del árbol de Steiner que en grafos cuasi-bipartitos tiene una razón de aproximación de 1.28. La complejidad del algoritmo de Robins y Zelikovsky es O( m n ² ) , donde m y n son el número de terminales y no terminales en el grafo, respectivamente. En 2012, Goemans et al. ^{[ 6 ]} proporcionó un algoritmo de aproximación de 73/60 ≈ 1,217 para el problema del árbol de Steiner en grafos cuasi-bipartitos; anteriormente se conocía un algoritmo que lograba el mismo factor de aproximación para el caso especial de grafos cuasi-bipartitos con aristas de costo unitario. ^{[ 7 ]}