8
$\begingroup$

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

Improve this question
$\endgroup$
1
  • $\begingroup$ This is an interesting question. I need to read up on the answers. $\endgroup$
    – Tayfun Pay
    Commented Dec 21, 2014 at 3:53

2 Answers 2

Reset to default
10
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Chandra, is there a convenient survey on submodular maximization one could link to ? $\endgroup$
    – Suresh Venkat
    Commented Dec 6, 2010 at 22:34
  • 3
    $\begingroup$ 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 $\endgroup$
    – Chandra Chekuri
    Commented Dec 6, 2010 at 22:43
  • $\begingroup$ 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. $\endgroup$
    – Grigory Yaroslavtsev
    Commented Dec 7, 2010 at 1:07
  • $\begingroup$ Can constant approximation factor be obtained without linear programming, e.g. using some greedy algorithm? $\endgroup$
    – Grigory Yaroslavtsev
    Commented Dec 7, 2010 at 15:00
  • 2
    $\begingroup$ 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. $\endgroup$
    – Aaron Roth
    Commented Dec 7, 2010 at 15:12
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Grigory Yaroslavtsev
    Commented Dec 6, 2010 at 21:19
  • $\begingroup$ 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. $\endgroup$
    – Dana Moshkovitz
    Commented Dec 6, 2010 at 21:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.