Approximating the maximally balanced connected partition problem in graphs

✍ Scribed by Janka Chlebíková

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 572 KB
• Volume: 60
• Category: Article
• ISSN: 0020-0190
• DOI: 10.1016/s0020-0190(96)00175-5

✦ Synopsis

The approximability of the following optimization problem is investigated: Given a connected graph G = (YE), find the maximally balanced connected partition for G, i.e. a partition (K, V2) of V into disjoint sets VI and V2 such that both subgraphs of G induced by VI and & are connected, and maximize an objective function "balance", B( V,, V2) = min( IV, 1, I&l). We prove that for any E > 0 it is NP-hard (even for bipartite graphs) to approximate the maximum balance of the connected partition for G = (YE) with an absolute error guarantee of IV/'-'. On the other hand, we give a polynomial-time approximation algorithm that solves the problem within 4/3 even when vertices of G are weighted. The variation of the problem is equivalent to the Maximally Balanced Spanning Tree Problem studied by Galbiati, Maffioli and Morzenti ( 1995). Our simple polynomial-time algorithm approximates the solution of that problem within 1.072.