Ethan Sifferman

What is the Max-Cut problem?

Given an undirected graph G, how can we arrange the verticies of G into two disjoint partitions such that the number of edges that cross the two partitions is maximized?

Learn more: Max-Cut!

The max-cut problem in graph theory comes up for many applications such as VLSI. However, it is proven to be insolvable in polynomial time. Yet, we still regularly rely on the answer to this problem. That is why, although we cannot find one master algorithm to solve the problem for all types of graphs, we should try to solve it for as many different classes of graphs as we can.

However, max-cut is solvable in polynomial time for graphs including complete graphs and split-indifferance graphs.
Max-cut is NP-Hard for cubic graphs, split graphs, interval graphs, and more.
This research project is dedicated to determining whether Max-cut on unit interval graphs is in NP-Hard or P.

What are Unit Interval Graphs?

An interval graph is an undirected graph formed from a set of intervals on the real number line, with a vertex for each interval, and an edge between vertcies whose intervals overlap. A unit interval graph is an interval graph where each interval is the unit length. Unit interval graphs are synonomous with proper interval graphs.

Learn more: Unit Interval Graphs!

Max-Cut on Unit Interval Graphs

Unit Interval Graphs have many more special properties than Improper Interval Graphs, allowing for many DP and greedy algorithms on common HP-Hard problems. So although max-cut is NP-Hard on Improper Interval Graphs, it may not be NP-Hard for unit interval graphs.

However, this project is in progress. No polynomial-time algorithm has been discovered, and no NP-Hard reduction to Unit Interval Graphs has been found. Keep checking back for more info!

References

GitHub Repository

More coming soon!