# Maximum One Third Cut

I want to solve the following problem (This is a homework problem. Not looking for definite or complete answers):

Maximum One Third Cut:

• Input: An undirected graph G=(V,E) where V={1,2,...,n}, such that |V| is divisible by 3, and a positive integral weight function w:E to N (on edges).
• Goal: Fin a subset of vertices U subset of V such that |U|=|V|/3.
• Objective: Maximize the total weight of the edges between U and its complement.

Of course, you can do that using a full search of all the possiblities. I want a more efficient algorithm though.

I'm thinking about some sort of Local Search algorithm, like Steepest Ascent Hill Climbing (SAHC), or a variation thereof (Simulated Annealing, Random Restart etc.).

• States:
Could be a binary vector, where the i-th element represents whether the vertex i is in U or not (0: not in U, 1: in U), where the number 1-s is |V|/3.
• Successors:
Turn one bit off, turn another on.
• Heuristic Function:
Sum of all weights of edges between U and V\U. Could be computed when generating a successor, you only need to check the vertex removed and added. Perhaps states can contain a list of edges that are relevant.
• Other Parameters:
Like Temprature or amount of restarts allowed could be set by testing the algorithm on graphs of varying in size, weight function and edges, and choosing the best values.

I was also thinking about Evolutionary Search.

Am I on the right track here? Are there better options perhaps? Any suggestions would be much appreciated.

Thanks!

• Your problem is probably NP-complete, so you're limited to heuristic algorithms. The performance of such heuristics depend on the graphs you run them on, and absent any theory, this is a purely empirical question. Commented Mar 24, 2017 at 9:04
• Thanks for your reply Yuval! I shall edit the question as per your request. Regarding your answer, I am by no means, looking for a definite answer, or looking for someone else to solve the problem for me. Though I was hoping for someone more experienced than myself to let me know whether I'm on the right track generally, or whether I've missed something glaringly obvious or trivial, or if I'm completely off course, in order to perhaps save some time. If I understood your reply, you're saying what I described could work, but needs further testing? So I'm generally in the right direction?
– Idra
Commented Mar 24, 2017 at 9:45
• Unfortunately I'm not an expert on heuristic algorithms, so I can't help any further. Commented Mar 24, 2017 at 9:54