Portal de Periódicos da CAPES

On the Hardness and Approximability of Planar Biconnectivity Augmentation

2009; Springer Science+Business Media; Linguagem: Inglês

10.1007/978-3-642-02882-3_25

1611-3349

Carsten Gutwenger, Petra Mutzel, Bernd Zey,

Complexity and Algorithms in Graphs

Given a planar graph G = (V,E), the planar biconnectivity augmentation problem (PBA) asks for an edge set E′ ⊆ V×V such that G + E′ is planar and biconnected. This problem is known to be $\mathcal{NP}$ -hard in general; see [1]. We show that PBA is already $\mathcal{NP}$ -hard if all cutvertices of G belong to a common biconnected component B *, and even remains $\mathcal{NP}$ -hard if the SPQR-tree of B * (excluding Q-nodes) has a diameter of at most two. For the latter case, we present a new 5/3-approximation algorithm with runtime ${\mathcal{O}}(|V|^{2.5})$ . Though a 5/3-approximation of PBA has already been presented [12], we give a family of counter-examples showing that this algorithm cannot achieve an approximation ratio better than 2, thus the best known approximation ratio for PBA is 2.