Computation of Normalized Cuts of Graphs

Abstract

The Normalized Cut problem was introduced by Shi and Malik in 1997. In a graph, a normalized cut is a partition of the vertices into two sets, where we minimize the cut value over the volume of the separated vertex sets, in an attempt to find a balanced cut. By minimizing the normalized cut, the association between the vertices within the two vertex sets is maximized and the disassociation between the vertices in the two vertex sets is minimized. Next to splitting the graph into two pieces, we can also split the graph in k pieces (a k-cut). There are two common ways to calculate the normalized cut value of a k-cut: we can either minimize the total sum of all the cuts (Normalized k-Cut) or we can minimize the maximum value of all the cuts (Max Normalized k-Cut). These forms of cutting a graph are useful in several fields, for instance, oceanography, discrete mathematics and theoretical computing science. In oceanography the Normalized Cut is widely used. Shi and Malik presented an algorithm using eigenvectors and they proved the Normalized Cut problem to be NP-complete. However, there is a distinct lack of further results on the hardness and fixed parameter tractability of this problem, which motivates our main research question of this thesis: What is the computational complexity of the Normalized Cut problem?

In this thesis we prove the Normalized Cut problem to be NP-complete for the vertex cover number equal to 2. We prove the Normalized k-Cut problem to be NP-complete for the vertex cover number equal to 3 and 4 and k = 3 or k = 4 respectively. Furthermore, we prove the Max Normalized k-Cut problem to be NP-complete when k equals the vertex cover number. These hardness results follow from a reduction from the Partition problem. The reductions from Partition hint that the weights of the edges are of influence on the difficulty of these problems.

For the Normalized Cut, Max Normalized 2-Cut, Normalized $k$-Cut and the Max Normalized $k$-Cut problems we present algorithms parameterized by treewidth or the vertex cover number. It stands out that we have the total sum of the edge-weights as extra parameter in the running times of these algorithms. For the Unweighted Normalized k-Cut and the Unweighted Max Normalized k-Cut problems we present algorithms parameterized by treewidth or the vertex cover number in which the total number of edges is part of the running time.