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?

In layman’s terms: picture someone’s schedule, full of a bunch of overlapping 1-hour meetings. The meetings all start at random times throughout the day, and many meetings conflict with one another. You want to give some of your meetings to someone else with a clear schedule such that the number of conflicts that each of your schedules hold is minimized.

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 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 was dedicated to determining whether Max-cut on unit interval graphs is in NP-Hard or P. However no conclusion was reached.

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, after spending 8 months on the problem, no conclusion was reached. We suspect that an NP reduction exists, but we were not able to find it.

Links