Simple Cuts Are Fast and Good: Optimum Right-Angled Cuts in Solid Grids

摘要

We consider the problem of bisecting a graph, i.e. cutting it into two equally sized parts while minimising the number of cut edges. In its most general form the problem is known to be NP-hard. Several papers study the complexity of the problem when restricting the set of considered graphs. We attempt to study the effects of restricting the allowed cuts. We present an algorithm that bisects a solid grid, i.e. a connected subgraph of the infinite two-dimensional grid without holes, using only cuts that correspond to a straight line or a right angled corner. It was shown in [13] that an optimal bisection for solid grids with n vertices can be computed in O(n~5) time. Restricting the cuts in the proposed way we are able to improve the running time to O(n~4). We prove that these restricted cuts still yield good solutions to the original problem: The best restricted cut is a bicriteria approximation to an optimal bisection w.r.t. both the differences in the sizes of the partitions and the number of edges that are cut.