Approximating the Minimum k-Section Width in Bounded-Degree Trees with Linear Diameter
share
Minimum k-Section denotes the NP-hard problem to partition the vertex set of a graph into k sets of sizes as equal as possible while minimizing the cut width, which is the number of edges between these sets. When k is an input parameter and n denotes the number of vertices, it is NP-hard to approximate the width of a minimum k-section within a factor of n^c for any c<1, even when restricted to trees with constant diameter. Here, we show that every tree T allows a k-section of width at most (k-1) (2 + 16n / diam(T) ) Δ(T). This implies a polynomial-time constant-factor approximation for the Minimum k-Section Problem when restricted to trees with linear diameter and constant maximum degree. Moreover, we extend our results from trees to arbitrary graphs with a given tree decomposition.
READ FULL TEXT