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

##### Summary

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.