Project Overview#

A cut is a vertex or edge set whose removal separates a graph into two disconnected parts. The cut is balanced if the two parts are of similar size. The problem of finding small balanced cuts arises in many applications involving graph partitioning, but finding minimal balanced cuts is NP-hard.

In contrast, minimal S-T cuts, which are cuts separating two given vertices S and T, can be found in polynomial time, but offer no balance guarantees. Worse, classical algorithms for finding minimal S-T cuts tend to return extreme solutions amongst the set of minimal S-T cuts, often leading to maximal imbalance. In this project we investigate the space of minimal S-T cuts, and how algorithms can be adapted to provide more balanced minimal S-T cuts.


  • This project requires students to have a strong background in data structure and algorithms and excellent programming skills C/C++/Java. ANU students are expected to have finished COMP3600 or have an equivalent experience.

Graph Research Lab#

Graph algorithms provide fundamental and powerful ways of exploiting the structure of graphs. Recent advances in machine learning, particularly deep learning, are also achieving remarkable results in a wide variety of application domains. Graph Research Lab @ ANU aims to investigate graph-related problems by marrying the best of two worlds: traditional graph algorithms and new machine learning techniques to bridging the gap between combinatorial generalisation and deep learning.

For further information about our team, visit our Github.


bars search times arrow-up