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, privacy policy and cookie policy

Browse other questions tagged or ask your own question.