<p>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 <em>balanced separator</em> problem, where each side is required to have a large fraction of the vertices. This may be what you are looking for.</p>

<p>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.</p>

CC BY-SA 2.5
2010-12-06T21:19:09.460Z
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?
Grigory Yaroslavtsev
CC BY-SA 2.5
2010-12-06T21:52:06.073Z
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.
Dana Moshkovitz
CC BY-SA 2.5
2010-12-06T19:46:22.767Z
2010-12-06T19:46:22.767Z
Dana Moshkovitz
<p>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.
<a href="https://doi.org/10.1023/B:JOCO.0000038913.96607.c2" rel="nofollow noreferrer">https://doi.org/10.1023/B:JOCO.0000038913.96607.c2</a></p>
<p>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.</p>

CC BY-SA 2.5
2010-12-06T22:34:46.640Z
Chandra, is there a convenient survey on submodular maximization one could link to ?
Suresh Venkat
CC BY-SA 2.5
2010-12-06T22:43:09.807Z
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. http://www.math.mcgill.ca/~vetta/Workshop/chekuri.pptx
Chandra Chekuri
CC BY-SA 2.5
2010-12-07T01:07:44.327Z
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.
Grigory Yaroslavtsev
CC BY-SA 2.5
2010-12-07T15:00:29.873Z
Can constant approximation factor be obtained without linear programming, e.g. using some greedy algorithm?
Grigory Yaroslavtsev
CC BY-SA 2.5
2010-12-07T15:12:52.173Z
Section 2 of this paper: http://www.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.
Aaron Roth
CC BY-SA 4.0
2010-12-06T22:25:59.197Z
2023-02-16T10:56:41.303Z
2023-02-16T10:56:41.303Z
Chandra Chekuri
<p>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$?</p>

<p>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|)$?</p>

CC BY-SA 3.0
2014-12-21T03:53:08.920Z
This is an interesting question. I need to read up on the answers.
Tayfun Pay
<ds.algorithms><approximation-algorithms><max-cut>
Approximation algorithms for MAX-CUT, when sizes of partition sets are fixed
Grigory Yaroslavtsev
# Approximation algorithms for MAX-CUT, when sizes of partition sets are fixed

(Asked by: username_0 on 2010-12-06)

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|)$?

**Tags:** ds.algorithms, approximation-algorithms, max-cut
> **Comments:**
> **username_1**: This is an interesting question. I need to read up on the answers.  

---

## 2 answers

### Answer by username_3 on 2010-12-06. Score: 10 | Accepted answer

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.
<https://doi.org/10.1023/B:JOCO.0000038913.96607.c2>

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.

> **Comments:**
> **username_4**: Chandra, is there a convenient survey on submodular maximization one could link to ?  
> **username_3**: 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. http://www.math.mcgill.ca/~vetta/Workshop/chekuri.pptx  
> **username_0**: 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.  
> **username_0**: Can constant approximation factor be obtained without linear programming, e.g. using some greedy algorithm?  
> **username_5**: Section 2 of this paper: http://www.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.  

---

### Answer by username_2 on 2010-12-06. Score: 3

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.

> **Comments:**
> **username_0**: 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?  
> **username_2**: 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.  

---

