How to Cut a Graph into Many Pieces

摘要

In this paper we consider the problem of finding a graph separator of a given size that decomposes the graph into the maximum number of connected components. We present the picture of the computational complexity and the approximability of this problem for several natural classes of graphs. We first provide an overview of the hardness of approximation of this prob lem, which stems mainly from its close relation to the Independent Set and to the Maximum Clique problem. Next, we show that the problem is solv able in polynomial time for interval graphs and graphs of bounded treewidth. We also show that MaxiNum Components is fixed-parameter tractable on planar graphs with the size of the separator as the parameter. Our main contribution is the derivation of an efficient polynomial-time approximation scheme for the problem on planar graphs.