Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs

摘要

The Max-Bisection and Min-Bisection problems are to find a partition of the vertices of a graph into two equal size subsets that respectively maximizes or minimizes the number of edges with endpoints in both subsets. We design the first polynomial time approximation scheme for the Max-Bisection problem on arbitrary planar graphs solving a long time standing open problem. The method of solution involves designing exact polynomial time algorithms for computing optimal partitions of bounded treewidth graphs, in particular Max- and Min-Bisection, which could be of independent interest. Using similar method we design also the first polynomial time approximation scheme for Max-Bisection on unit disk graphs (which could be easily extended to other geometrically defined graphs).