I have this problem. I have a graph of n nodes that I want to split into two subgraphs of x nodes and n-x nodes subject to the constraint that the number of remaining edges is maximized (or minimizing the number of edges that are cut).
Not sure if that makes sense. Not a graph theory person but this is the abstract version of my problem. What algorithms should I look at that might help me?
This is NOT a homework problem. Interesting problem though I think!
I plan on implementing in C.
The special case where x = n - x is called the minimum bisection problem and is NP-hard. This makes your problem NP-hard as well. There are several heuristics described in the Wikipedia article on graph partitioning, including local search (e.g., start with a random cut and repeatedly swap pairs of vertices that decrease the size of the cut) and spectral methods (e.g., compute and threshold the second eigenvector). If n is small, integer programming is also a possibility.