The question is: given a planar graph $G$ with unit capacity edge weights and a fixed positive integer $k$, what is an approximation algorithm for finding the minimum size of a cut $(A,B)$ with $|A|=k$ and $|B| = |V(G)|-k$?

I know that when $k=|V(G)|/2$, this is known as the minimum bisection problem, NP-hard for general graphs and unknown for planar graphs (https://www.sciencedirect.com/science/article/pii/S1571065315001134 and https://mediatum.ub.tum.de/doc/1338548/1338548.pdf)

For arbitrary fixed $k$, I'm not sure what the standard terminology for this question is, though Peng Zhang refers to it as the min E$k$-size cut problem: https://link.springer.com/article/10.1007/s11704-014-3289-1. In this paper, an $O(\log n)$ approximation algorithm is given for the min $Ek$-size cut problem, but this is not specific to planar graphs or graphs with unit capacity weight. Are there better approximation algorithms for graphs that are planar and have unit capacity weights?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.