On the Complexity of the Normalized Cut Problem on H-Free Graph Classes

Abstract

The Normalized Cut problem is a graph partitioning problem that is known to be NP-complete in general. Therefore, we look into the complexity of the Normalized Cut problem on certain H-free graph classes. H-free graphs are those which do not contain any graph of H as an induced subgraph, for any fixed set of graphs H. We show that the Normalized Cut problem is NP-complete on claw-free, split, and complete graphs. Furthermore, we show that the Normalized Cut problem with unweighted edges is strongly NP-complete in general. On the other hand, we show that the partition with minimum normalized cut value has two connected components and use this property to construct polynomial-time algorithms on certain H-free graph classes. We show that we can solve the Normalized Cut problem on forests in linear time and on outerplanar graphs in quadratic time. Furthermore, we show that we can solve the Normalized Cut problem with unweighted edges on cactus and cluster graphs in linear time. Lastly, we observe that there exists an O(log(n))-approximation algorithm for another graph partitioning problem to which we can reduce the Normalized Cut problem. Therefore, we have an O(log(n))- approximation algorithm for the Normalized Cut problem.