Approximation algorithms for MAX-CUT, when sizes of partition sets are fixed

The MAX-CUT problem has constant factor approximation, but we can't control the sizes of the sets in resulting partition. What is known about maximizing cut size, if we restrict one part of the partition to have size exactly $k$?

Formally, given a graph $G(V, E)$ and integer $k$, find the set $S \subset V$, such that $|S| = k$ and the number of edges between $S$ and $V \setminus S$ is maximized. What is the name of this problem (for example, if $k = |V|/2$, this is known as MAX-BISECTION)? Does it become easier to approximate in polynomial time, if $k$ is $polylog(|V|)$?

• This is an interesting question. I need to read up on the answers. Dec 21 '14 at 3:53

There is a 1/2-approximation for Max-Cut with a given size k where k is part of the input. This is in a paper of Ageev and Sviridenko on pipage rounding. See below. http://www.springerlink.com/content/r37k4302n7m17427/

The above problem is an example of submodular function maximization subject to a matroid base constraint. There has been much recent work on submodular function maximization subject to a variety of constraints.

• Chandra, is there a convenient survey on submodular maximization one could link to ? Dec 6 '10 at 22:34
• Not yet. Progress is being made on some basic questions and there is a plan to write a survey in the (near?) future. In the mean time I can point to a talk I gave in March of this year which has some pointers. It is not meant to be a survey though the title says it. math.mcgill.ca/~vetta/Workshop/chekuri.pptx Dec 6 '10 at 22:43
• Thank you, Chandra! I will need some time to look carefully through the paper. However, the intro clearly states the result you mentioned and it is the type of result I wanted to find. Dec 7 '10 at 1:07
• Grigory, if this is what you want, you might consider "accepting" the answer. Dec 7 '10 at 6:31
• Section 2 of this paper: cs.cmu.edu/~alroth/Papers/submodularsecretary.pdf gives a constant factor approximation for this problem using a greedy algorithm. This is -not- the best known approximation factor, but it is probably the simplest algorithm. Dec 7 '10 at 15:12

I don't know of a name for the Max-Cut problem where one side of the cut is restricted to be of size k. There is the balanced separator problem, where each side is required to have a large fraction of the vertices. This may be what you are looking for.

If one side of the cut is of size k, then there is an (n choose k) time algorithm. So if k=polylogn, there is a quasi-polynomial time algorithm for the problem, and it's not NP-hard.

• Thank you, it looks like I need to ask more specifically. I cannot relax the problem to balanced separator setting, because $k$ should really be fixed and I want a polynomial-time algorithm, not quasi-polynomial. So the question is whether we can have this, allowing ourselves to have just constant-factor approximation, not exact solution? Dec 6 '10 at 21:19
• My bet would be that the approximation problem you describe, where k is poly-logarithmic, is not in P under plausible complexity assumptions, but I don't know of a reference. Dec 6 '10 at 21:52