Chicago Journal of Theoretical Computer Science

The MIT Press

Volume 1997, Article 2 3 June 1997

ISSN 1073–0486. MIT Press Journals, Five Cambridge Center, Cambridge, MA 02142-1493 USA; (617)253-2889; journals-orders@mit.edu, journals-info@mit.edu. Published one article at a time in L^{A}TEX source form on the Internet. Pagination varies from copy to copy. For more information and other articles see:

• http://www-mitpress.mit.edu/jrnls-catalog/chicago.html

• http://www.cs.uchicago.edu/publications/cjtcs/

• ftp://mitpress.mit.edu/pub/CJTCS

• ftp://cs.uchicago.edu/pub/publications/cjtcs Kann et al. Hardness of Approximating Max k-Cut (Info)

The Chicago Journal of Theoretical Computer Science is abstracted or indexed in Research Alert,◯^{R}SciSearch,◯^{R}Current Contents◯^{R}/Engineering Computing & Technology, and CompuMath Citation Index.◯^{R}

\begin{matrix}c \\ ◯ \end{matrix}1997 The Massachusetts Institute of Technology. Subscribers are licensed to use journal articles in a variety of ways, limited only as required to insure fair attribution to authors and the journal, and to prohibit use in a competing commercial product. See the journal’s World Wide Web site for further details. Address inquiries to the Subsidiary Rights Manager, MIT Press Journals; (617)253-2864; journals-rights@mit.edu.

The Chicago Journal of Theoretical Computer Science is a peer-reviewed scholarly journal in theoretical computer science. The journal is committed to providing a forum for significant results on theoretical aspects of all topics in computer science.

Editor in chief: Janos Simon

Consulting editors: Joseph Halpern, Stuart A. Kurtz, Raimund Seidel

Editors:

Martin Abadi  Greg Frederickson John Mitchell
Pankaj Agarwal Andrew Goldberg Ketan Mulmuley
Eric Allender Georg Gottlob Gil Neiger
Tetsuo Asano  Vassos Hadzilacos David Peleg
Laszló Babai  Juris Hartmanis Andrew Pitts
Eric Bach  Maurice Herlihy James Royer
Stephen Brookes Ted Herman  Alan Selman
Jin-Yi Cai  Stephen Homer  Nir Shavit
Anne Condon  Neil Immerman  Eva Tardos
Cynthia Dwork Howard Karloff  Sam Toueg
David Eppstein Philip Klein  Moshe Vardi
Ronald Fagin  Phokion Kolaitis Jennifer Welch
Lance Fortnow Stephen Mahaney Pierre Wolper
Steven Fortune Michael Merritt

Managing editor: Michael J. O’Donnell

Electronic mail: chicago-journal@cs.uchicago.edu

[ii]

On the Hardness of Approximating Max k-Cut and Its Dual

Viggo Kann  Sanjeev Khanna  Jens Lagergren

Alessandro Panconesi

3 June, 1997

Abstract

We study the Max k-Cut problem and its dual, the

Abstract-1

Min k-Partition problem. In the Min k-Partition problem, given a graph G = (V, E) and positive edge weights, we want to find an edge set of minimum weight whose removal makes G k-colorable. For the Max k-Cut problem we show that, if P ≠ NP, no polynomial time approximation algorithm can achieve a relative error better than 1/(34k). It is well known that a relative error of 1/k is obtained by a naive randomized heuristic.

For the Min k-Partition problem, we show that for k > 2 and for

Abstract-2

every ϵ > 0, there exists a constant α such that the problem cannot be approximated within α|V |^{2−ϵ}, even for dense graphs. Both problems are directly related to the frequency allocation problem for cellular (mobile) telephones, an application of industrial relevance.

1 Introduction

To motivate the problems studied in this paper, consider the frequency alloca-

1-1

tion problem for cellular telephones. We are given a fixed set of k frequencies, and a set of radio transmitters. Moreover, for each pair of transmitters, we are given a number that represents the percentage of local performance deterioration incurred if the pair receives the same frequency. The problem is to allocate frequencies to radio transmitters so that the global performance deterioration is minimized. It is indeed natural to model this problem by a

Kann et al. Hardness of Approximating Max k-Cut §1

1 coloring problem for edge-weighted graphs. Vertices of the graph correspond to transmitters, and colors correspond to frequencies. Edges indicate nonzero local performance deterioration, and their weights indicate the percentages of local performance deterioration. Formally, the graph problem can be stated as follows:

��� k����������

Input: A graph G = (V, E), with weighted edges.

Goal: Find a color assignment c: V →[k] that minimizes the total weight of monochromatic edges (an edge is monochromatic if its endpoints have the same color).

In other words, we seek an edge set of minimum weight whose removal makes the graph k-colorable. This problem is relevant in industrial applications.^{1}

For k = 2, Garg, Vazirani, and Yannakakis [GVY96] use multicommodity

1-2

flow techniques to give a polynomial time O(log n)-approximation algorithm, where n denotes the number of vertices in the input graph G. The problem is MAX SNP-hard; the best lower bound known for the approximation of Max Cut (i.e., Max k-Cut with k = 2) translates into a 1.058 lower bound for Min 2-Partition . Shrinking this gap between upper and lower approximation bounds appears to be a challenging open problem.

When k ≥ 3, a result of Petrank implies that it is NP-hard to approx-

1-3

imate Min k-Partition within O(n) [Pet94]. This result, however, holds only for “sparse” graphs, that is, graphs with O(n) edges. Petrank left the approximability of Min k-Partition for nonsparse graphs as an open question. Edwards [Edw86] and Arora, Karger, and Karpinski [AKK95] have shown that 3-colorability is polynomial time solvable on graphs where each vertex has degree at least ϵn for some constant ϵ > 0.

In this paper, we continue this line of research by showing that, for k ≥ 3:

1-4

• For every fixed ϵ > 0 and every δ < (1 − 1/k)/2, it is NP-hard to approximate Min k-Partition within O(n^{2−ϵ}), even when the problem is restricted to dense graphs with |E| = δn^{2}. If δ > (1 − 1/k)/2, the graph is certainly not k-colorable by Turán’s theorem [Tur41] (see

2 a standard graph theory text such as [Wes96], for instance), and the whole graph is trivially a constant factor approximation.

1Many problems that appear in applications have the problem formulated here as a special case. However, in this paper we are interested in lower bounds, and therefore our results apply directly to these problems.

• It is NP-hard to approximate Min k-Partition within O(|E|), even when restricting to graphs with |E| = Ω(n^{2−ϵ}).

• Min 3-Partition can be approximated within ϵn^{2}, for every ϵ > 0. This completes the picture as far as the densities are concerned, and answers completely the open question of Petrank.

In view of the above two negative results, it seems natural to consider the

1-5

dual problem:

��� k����

Input: A graph G = (V, E) with weighted edges.

Goal: Find a color assignment c: V → [k] that maximizes the total weight of properly colored edges (an edge is properly colored if its endpoints have different colors).

There are many interesting theoretical results on this problem. In particular, the Max Cut problem has received much attention (see [GW95, PT95], for example). In a seminal paper, Papadimitriou and Yannakakis [PY91] showed that the problem is MAX SNP-complete. Recent results in the theory of probabilistic checking of proofs provide powerful new tools for proving hardness of approximation results, under suitable complexity theoretic assumptions (see [BGS95] for an overview). The best-known lower bound on the relative error achievable for Max Cut is 0.0588, under the assumption P ≠ NP [Hås97]. For Max k-Cut it is well known that a naive randomized heuristic achieves a relative error of 1/k: Each vertex is assigned one of the k colors uniformly at random. This simple procedure can be derandomized by a straightforward application of the method of conditional probabilities (see [MR95], for example).

For the case k = 2, the above heuristic algorithm has a relative error

1-6

bound of 0.5, a bound that held for about two decades until the recent pioneering work of Goemans and Williamson [GW95]. Their techniques—a beautiful blend of mathematical programming and probabilistic methods— yield a relative error bound of 0.122 [GW95]. More recently, Frieze and

3 Jerrum [FJ95] have tried to generalize the Goemans and Williamson technique to the Max k-Cut problem. Their results are quite interesting from a technical point of view but yield only a marginal improvement—from 1/k to (roughly) 1/k −2k^{−2} ln k. It is natural to ask whether better approximations are possible, say, a relative error of 1/k^{1+ϵ}, for some ϵ > 0. In this paper, we give (under the assumption P ≠ NP) a negative answer to this question. We show that if P ≠ NP, for each k ≥ 2 the true relative error bound for approximating Max k-Cut lies between 1/k and 1/σk, where currently σ = 34 (the value of σ depends on the best lower bound available on the approximation of Max Cut ). Hence, unless P = NP, we cannot hope for relative error bounds like 1/k^{1+ϵ} or even, say, 1/(k log log … log k). On the other hand, the naive randomized heuristics achieve a relative error that is very close to the best possible (assuming P ≠ NP).

A few words on the techniques used in this paper. The Max k-Cut

1-7

result is obtained by making use of an approximation preserving reduction from Max Cut . The difficulty in the proof is to exhibit a reduction that increases the relative error only linearly as a function of k. The proof uses the probabilistic method and a construction involving the Hamming distance between characteristic vectors. Our reduction to Max k-Cut increases the relative error by approximately a factor of 2k. In contrast, the original reduction in [PY91] increases the relative error by a factor greater than 1000k^{2}. The Min k-Partition lower bound of Ω(n^{2−ϵ}) is obtained by amplifying the NP-hardness of k-coloring into a zero versus Ω(n^{2−ϵ}) separation. The ϵn^{2}-approximation algorithm is based on the fact that 3-colorability can be solved in polynomial time for dense instances [Edw86, AKK95].

We emphasize that our hardness results do not depend on the existence

1-8

of exponentially large weights in the input instances; in fact, they also hold for the unweighted case (see also [CST95]).

This paper is organized as follows. Section 2 defines the notion of approx-

1-9

imation preserving reductions used in this paper. In Section 3, we present the hardness result for Max k-Cut and a precise lower bound computation using the currently best-known lower bound for Max Cut . Finally, in Section 4, we present our upper and lower bounds for approximating Min k-Partition .

4

2 Definitions

We will use the standard approximation terminology. See for example [CK95]

2-1

for detailed definitions.

Solving an optimization problem F given the input instance x means

2-2

finding a solution y such that the value of the objective function m_{F} (x, y) is equal to the optimum (maximum or minimum). Let opt_{F} (x) denote this optimum value of m_{F}.

Approximating an optimization problem F given the input x means find-

2-3

ing some feasible solution y. How good the approximation is depends on the relation between m_{F} (x, y) and opt_{F} (x). There are two equivalent measures of this relation: The performance ratio and the relative error. The performance ratio of a solution y to an optimization problem F is defined as

R_{F} (x, y) = max \{\frac{opt_{F} (x)}{m_{F} (x, y)}, \frac{m_{F} (x, y)}{opt_{F} (x)}\}

The relative error is defined as

E_{F} (x, y) = \frac{|opt_{F} (x) − m_{F} (x, y)|}{opt_{F} (x)}

These definitions are only meaningful when opt_{F} (x) ≠ 0. This is a prob-

2-4

lem for Min k-Partition when the input graph is k-colorable. To make the definition robust and to simplify the statement of our results, we define the optimum value for Min k-Partition as max{1, min_{c} m(G, c)} where G = (V, E) is the input graph, c ranges over all possible color assignments c: V →{1, …, k}, and m(G, c) measures the number of monochromatic edges under c.

An optimization problem F can be approximated within f(n) for a func-

2-5

tion f if there exists a polynomial time algorithm A such that for all input instances x, A(x) is a feasible solution and R_{F} (x, A(x)) ≤ f(|x|). The algorithm A(x) is called an f(n)-approximation algorithm.

Although various reductions preserving approximability within constants

2-6

have been proposed (see [CKST95]), the L-reduction defined in [PY91] is perhaps the easiest to use. Given two NP optimization problems F and G, an L-reduction from F to G consists of two polynomial-time computable functions f and g and two positive constants α and β, such that f transforms instances of F into instances of G, and such that, for every instance x of F,

5 • opt_{G}(f(x)) ≤ α · opt_{F} (x), and

• for every feasible solution y of f(x) with objective value m_{G}(f(x), y) = s_{2}, y′ = g(x, y) is a feasible solution of x with m_{F} (x, y′) = s_{1} such that |opt_{F} (x) − s_{1}| ≤ β|opt_{G}(f(x)) − s_{2}|.

The composition of L-reductions is also an L-reduction. If F L-reduces to

2-7

G with constants α and β and there is a polynomial time approximation algorithm for G with worst-case relative error ϵ, then there is a polynomial time approximation algorithm for F with worst-case relative error αβϵ [PY91]. Conversely, if δ is a lower bound for the approximation of F, then δ/(αβ) is a lower bound for G. An L-reduction from F to G, therefore, can be used both to show hardness of approximability (for G) and to find a new approximation algorithm (for F).

Given two k-dimensional vectors χ_{1} and χ_{2}, the Hamming distance be-

2-8

tween them is denoted by h(χ_{1}, χ_{2}). For a graph G and a vertex v of G, we denote the degree of v in G by d_{G}(v). If the edges of G have positive weights, the degree of a vertex v refers to its weighted degree, given by the sum of the weights of the edges incident on it. In this paper, a coloring of a graph G is any assignment of colors to the vertices, and a k-coloring is any coloring using at most k colors.

3 Hardness of Approximating ��� k����

In this section, we give an L-reduction from Max Cut to Max k-Cut . The

3-1

reduction maps a Max Cut instance G to a Max k-Cut instance H, and is such that:

• opt_{Max k-Cut} (H) ≤ k(k − 1)opt_{Max Cut} (G), i.e., α = k(k − 1), and

• given any Max k-Cut solution h with cost s_{h}, we can find in polynomial time a Max Cut solution g with cost s_{g} satisfying

|opt_{Max Cut} (G) − s_{g}| ≤ \frac{2}{k}|opt_{Max k-Cut} (H) − s_{h}|

i.e., β = 2/k.

This reduction together with a lower bound of the approximability of

3-2

Max Cut gives the following theorem.

6 Theorem 1 There is a constant σ between 1 and 34 such that it is NP-hard to approximate Max k-Cut with relative error less than \frac{1}{σ(k−1)}.

Proof of Theorem 1 A lower bound of δ for the relative error of Max Cut

Prove Theorem 1-1

will, using the L-reduction, give us a lower bound of \frac{δ}{αβ} = \frac{δ}{2(k−1)} for Max k-Cut . In Håstad [Hås97] it was shown that it is NP-hard to approximate Max Cut within 17/16, which gives us the lower bound 1/17 for the relative error, and the theorem follows.

Proof of Theorem 1 □

Remark 1 Better lower bounds for Max Cut will automatically give better lower bounds for Max k-Cut .

We now give the L-reduction from Max Cut to Max k-Cut . In the

3-3

proof, we assume that k is even, and we transform an unweighted graph G into a weighted graph H. These two restrictions can be assumed without loss of generality. The case when k is odd follows from the following simple reduction from Max k-Cut to Max (k + 1)-Cut : Given an instance H of the former, produce an instance H′ of the latter by adding an extra node u and connecting it to all vertices in H. All edges in H′ have weight 1, except edges of the form (u, x), x ∈ V (H), which have weight w(u, x) = d_{H}(u)/k. This is an L-reduction with α = (k + 1)/(k − 1) and β = 1. The proof is rather straightforward and hence is omitted. Just observe that one can assume without loss of generality that all cuts in H′ use color k + 1 for u and colors 1 through k for the isomorphic copy of H contained in H′. The second restriction (the fact that H is weighted, while G is not) could be eliminated by further refining the reduction to yield an unweighted instance of the Max k-Cut problem. This is not needed, however, in view of the more general result of Crescenzi, Silvestri, and Trevisan [CST95]. They show that for a rather general class of optimization problems, including Max k-Cut , the approximation ratios of the weighted and unweighted cases coincide, provided the weights are polynomially bounded. Our reduction below uses weights bounded by |V (G)|, and hence that result applies.

We now turn to the task of defining the L-reduction. The graph H is

3-4

defined as follows. Assume that V (G) = {v_{1}, …, v_{n}}. Let V_{1}, …, V_{k/2} be sets (of vertices) defined by V_{i} = {v_{1}^{i}, …, v_{n}^{i}}. That is, the sets V_{1}, …, V_{k/2} are “copies” of the vertex set of G. Actually, we will say that for every 1 ≤ i ≤ k/2, the vertex v_{l}^{i} is a copy of the vertex v_{l} of G. Let H be the graph with vertex set V_{1}, ∪ ⋯ ∪ V_{k/2} and with the following edges:

7 • If (v_{l}, v_{m}) is an edge of G, then (v_{l}^{i}, v_{m}^{j}) is an edge of H, for 1 ≤ i ≤

j ≤ k/2. These edges are called cross edges.

• All edges between all copies of the same vertex, i.e., for every vertex v_{l} of G and 1 ≤ i < j ≤ k/2, (v_{l}^{i}, v_{l}^{j}) is an edge of H. We will refer to these edges as the row edges, and the set of copies of v_{l} will be referred to as the row of v_{l}.

We make a few observations. First, the row of a vertex v_{l} induces a clique

3-5

in H which we call the row clique of v_{l}. Second, if we take two different rows, say, the row of u and the row of v such that (u, v) is an edge of G, then the cross edges between these rows induce a complete bipartite graph. Third, the subgraph of H induced by V_{i}, call it G_{i}, is isomorphic to G. Moreover, the map that maps the vertex v_{l} of G to the vertex v_{l}^{i} of G_{i} (i.e., to its copy in G_{i}) is an isomorphism. We will call the graphs G_{1}, …, G_{k/2} the G-copies.

Finally, the edge weights of H are defined as follows: All cross edges have

3-6

weight 1, whereas all edges in the row of v_{l} have weight equal to d_{G}(v_{l}). We denote the sum of the weights of the edges of H by w(H).

Lemma 1 opt_{Max k-Cut} (H) ≤ k(k − 1)opt_{Max Cut} (G).

Prove Lemma 1-1 Proof of Lemma 1 First, we prove that w(H) = \frac{k(k−1)}{2}|E(G)|. Notice that in H there are k/2 copies of each vertex u of G, and each such copy has weighted degree \frac{k}{2}d_{G}(u) + (\frac{k}{2} − 1)d_{G}(u) = (k − 1)d_{G}(u). Hence

w(H) = \frac{1}{2} ∑_{x∈V (H)} d_{H}(x) = \frac{k}{4} ∑_{u∈V (G)}(k − 1)d_{G}(u) = \frac{k(k − 1)}{2}|E(G)|

Since opt_{Max Cut} (G) ≥ |E(G)|/2 and opt_{Max k-Cut} (H) ≤ w(H) for all graphs G and H, the claim follows.

Proof of Lemma 1 □

Clearly, the graph H can be constructed in polynomial time, and it sat-

3-7

isfies the first requirement of the L-reduction. We now prove that the other requirement of the L-reduction is also satisfied. A coloring of H is said to be canonical if it satisfies the following:

• each G-copy is bichromatic,

• no two G-copies share a color, and 8

• all G-copies have exactly the same coloring up to renaming of the colors.

For each graph F and each coloring c of F, we define the cut-weight of c to be the sum of the weights of the bichromatic edges of F with respect to c; we denote it by cw(c, F).

Lemma 2 Given a k-coloring c of H, one can find in polynomial time a canonical k-coloring c′ with cut-weight at least as large as that of c.

Once the above lemma is established, it follows that the second require-

3-8

ment of the L-reduction is satisfied. We will now prove that this is the case.

Proof of Lemma 2 Given a coloring of G, we can find a canonical color-

Prove Lemma 2-1

ing of H; the above lemma effectively means that all k-colorings of H are canonical, including the optimum colorings. If c′ is canonical, its cut-weight is given by

cw(c′, H) = W + \frac{k}{2}cw(g, G)

where g is the coloring appearing in each G-copy, and W is the sum of the weights of all edges connecting vertices in different G-copies. In particular, an optimum coloring of H has cut-weight

W + \frac{k}{2}opt_{Max Cut} (G)

It follows that for c and c′ as in Lemma 2,

|opt_{Max k-Cut} (H) − cw(c, H)|

≥ |opt_{Max k-Cut} (H) − cw(c′, H)| = \frac{k}{2}|opt_{Max Cut} (G) − cw(g, G)|

and so the second requirement of the L-reduction is satisfied with β = 2/k. The first step in proving Lemma 2 is to show that we may assume without

Prove Lemma 2-2

loss of generality that each row is properly colored, that is, it is colored with k/2 colors.

Lemma 3 For each k-coloring c_{0} of H, there is a k-coloring c of H such that cw(c, H) ≥ cw(c_{0}, H), and each row edge is bichromatic with respect to c. Moreover, given c_{0} and H, the k-coloring c can be obtained in polynomial time.

9 Proof of Lemma 3 Assume that x and y are two copies in H of the same

Prove Lemma 3-1

vertex u of G, such that c_{0}(x) = c_{0}(y) = p. For each color p′ that is not used in the row of u, let A_{p′} be the set of vertices z adjacent to x in H such that c_{0}(z) = p′. Notice that for every such set A_{p′}, an edge between x and a vertex of A_{p′} is a cross edge. Since there are more than k/2 such colors p′, and the number of cross edges incident to x is \frac{k}{2}d_{G}(u), it follows that there is a p′ such that |A_{p′}| < d_{G}(u). If we recolor x with p′, we create at most |A_{p′}| monochromatic edges of weight 1, but get rid of one monochromatic (row) edge of weight d_{G}(u). Thus, by recoloring x with p′ we obtain a coloring of greater cut-weight. This process can be repeated until, in polynomially many steps, we have a new coloring that satisfies the stated properties.

Proof of Lemma 3 □

Now fix a k-coloring c of H. By the previous lemma, we may assume that

Prove Lemma 2-3

every row edge is bichromatic with respect to c. For each vertex u of G, let χ(u) be the vector in {0, 1}^{k} defined by χ(u)_{p} = 1 if and only if the color p is used in the row of u in H. Notice that by the choice of c, each vector χ(u) has a Hamming weight of cardinality k/2 (recall that the Hamming weight of a vector is the number of its nonzero coordinates).

Given c, we now construct a canonical coloring c′. The crux of the ar-

Prove Lemma 2-4

gument is to show how to compute a canonical coloring c′ whose number of monochromatic edges is no more than that of c. This implies that the cut-weight of c′ is no less than the cut-weight of c.

Roughly speaking, the difficulty of the proof, and what makes it interest-

Prove Lemma 2-5

ing, is to show how, given c, one can get rid of the bichromatic cross edges connecting vertices in different G-copies. Local exchange arguments such as those used in Lemma 3 do not seem applicable, and we solve the problem by making use of the vectors χ(u) and the probabilistic method.

Our next step is to count the number of monochromatic edges with respect

Prove Lemma 2-6

to c as a function of the Hamming distance between the χ(·) vectors.

Lemma 4 Let u and v be two vertices of G such that (u, v) is an edge of G. The number of monochromatic cross edges between the row of u and the row of v is (k − h(χ(u), χ(v)))/2.

Proof of Lemma 4 Let P be the set of colors that appear in both rows.

Prove Lemma 4-1

Since χ(u) and χ(v) are both k-dimensional and have Hamming weight k/2

10 each, it follows that

|P | = \frac{k − h(χ(u), χ(v))}{2}

Since each color has at most one occurrence per row and the cross edges between the two rows induce a complete bipartite graph, |P | equals the number of monochromatic edges.

Proof of Lemma 4 □

We now use the χ(·) vectors to find a good 2-coloring of G that can

Prove Lemma 2-7

be duplicated in each G-copy, using new colors in each G-copy. Chose i uniformly at random between 1 and k, and let r be the 2-coloring of G defined by r(v) = χ(v)_{i}. It follows immediately that for every two vertices u and v of G, we have

Pr[r(u) = r(v)] = \frac{k − h(χ(v_{l}), χ(v_{m}))}{k}

We also get the following lemma for the expectation of the number of monochromatic edges of G with respect to r. Lemma 5

E[|Mono (G, r)|] = \frac{2}{k}|Mono (H, c)|

where Mono (G, r) is the set of monochromatic edges of G with respect to r.

Proof of Lemma 5 First notice that

Prove Lemma 5-1

|Mono (H, c)| = ∑_{(u,v)∈E(G)}|Mono (G, c) ∩ Cross (G, u, v)|

= \frac{1}{2} ∑_{(u,v)∈E(G)}(k − h(χ(u), χ(v)))

where Cross (G, u, v) is the set of cross edges in G between the row of u and the row of v. The last equality follows from Lemma 4. From this we get

E[|Mono (G, r)|] = ∑_{(u,v)∈E(G)} Pr[r(u) = r(v)]

= ∑_{(u,v)∈E(G)} \frac{k − h(χ(u), χ(v))}{k} = \frac{2}{k}|Mono (H, c)|

Proof of Lemma 5 □

11 Clearly, for at least one 2-coloring g of G, the number of monochromatic

Prove Lemma 2-8

edges is at least the expected value. We can find such a 2-coloring simply by computing, for all values of i, the number of monochromatic edges given by the coloring r(v) = χ(v)_{i}. To obtain a canonical c′, just color each G-copy according to g, each time using new colors. The whole process can be carried out in polynomial time.

Proof of Lemma 2 □

4 Hardness of Approximating ��� k����������

We now show that for each fixed k > 2, it is NP-hard to approximate

4-1

Min k-Partition to within a factor of O(n^{2−ϵ}) for every ϵ > 0. An interesting aspect of this result is that it holds even when we restrict ourselves to graphs with Ω(n^{2−ϵ}) edges.

Definition 1 (Dense and Everywhere Dense Graphs) An n-vertex graph is called dense if it has Ω(n^{2}) edges, and it is called (everywhere) ϵ-dense if each vertex in the graph has degree at least ϵn for some fixed ϵ > 0.

We begin with the following simple lemma.

4-2

Lemma 6 For each k ≥ 3, it is NP-hard to decide if a graph is k-colorable over graphs with Θ(n^{α}) edges, where 0 < α ≤ 2.

Proof of Lemma 6 It suffices to show that the result holds on the family

Prove Lemma 6-1

of n-vertex graphs with Ω(n^{2}) edges (i.e., dense graphs): We can obtain a graph with Θ(n^{α}) edges by adding a disjoint empty graph on Θ(n^{2/α}) vertices. Clearly, this transformation leaves the chromatic number unchanged.

We show only the hardness of 3-coloring on dense graphs: Edwards [Edw86]

Prove Lemma 6-2

proved that for k ≥ 4, k-coloring a dense graph is NP-hard. Given a graph G on n vertices, we construct another graph G′, which is simply a disjoint union of G and a complete 3-partite graph H on N vertices such that each part of the partition has the same size. If we choose N to be the smallest multiple of 3 greater than or equal to n^{2}, then clearly the graph G′ is dense. Furthermore, it is immediate from the construction that G′ is 3-colorable if and only if G is 3-colorable. Hence it is NP-hard to decide if a dense graph is 3-colorable.

Proof of Lemma 6 □

12 From here on, we use γ(G, k) to denote the minimum number of edges that

4-3

must be deleted from G to obtain a k-partite graph. The next lemma shows that the NP-hardness of distinguishing between γ(G, k) = 0 and γ(G, k) ≥ 1 can be amplified to that of distinguishing between γ(H, k) = 0 and γ(H, k) = Ω(n^{2−ϵ}) for each fixed ϵ > 0. This yields the desired hardness result. The precise statement is as follows.

Lemma 7 (Amplification Lemma) For all positive integers k and s, given a graph G, one can in polynomial time construct a graph H such that |V (H)| = s|V (G)|, |E(H)| = s^{2}|E(G)|, and γ(H, k) = s^{2}γ(G, k).

Proof of Lemma 7 The graph H in the Amplification lemma is constructed

Prove Lemma 7-1

as follows:

• For each vertex u in G, the set V (H) contains s copies named u_{1}, …, u_{s}.

• (u_{i}, v_{j}) is an edge in H if and only if (u, v) is an edge in G.

Notice that the set of copies of each vertex u, that is, u_{1}, …, u_{s}, is an independent set of H. It is easily seen that |V (H)| = s|V (G)|, |E(H)| = s^{2}|E(G)|, and that the construction can be done in polynomial time. In the remainder of this section, H will denote the graph obtained from G by the construction above.

Prove Lemma 7-2

Definition 2 (Quasi-coloring) A coloring of a graph G is called an ⟨m⟩ quasi-coloring if it induces at most m monochromatic edges.

We say that an ⟨m⟩ quasi-coloring of H is normalized if and only if, for each u ∈ V (G), all the s copies of u in H, that is, u_{1}, …, u_{s}, have the same color.

Lemma 8 Each ⟨m⟩ quasi-coloring of H can be transformed into a normalized ⟨m⟩ quasi-coloring in polynomial time.

Proof of Lemma 8 Let c be a given ⟨m⟩ quasi-coloring. Consider any ver-

Prove Lemma 8-1

tex u in G and let u_{min} be the copy of u in H with the smallest number of monochromatic edges incident on it under the coloring c. Since the u_{i}s have the same neighbors, the coloring c′ that assigns the color of the vertex u_{min} to each copy u_{i}, and agrees with coloring c everywhere else, is still an ⟨m⟩ quasi-coloring. Iterating this process over each vertex u in G, we get a normalized ⟨m⟩ quasi-coloring for H.

Proof of Lemma 8 □

13 We can now prove that he graph H constructed above satisfies γ(H, k) =

Prove Lemma 7-3

s^{2}γ(G, k). Every ⟨m⟩ quasi-coloring of G can be transformed into an ⟨s^{2}m⟩ quasi-coloring for H. For each vertex u in G, assign its color to all the copies of u in H. Thus γ(H, k) ≤ s^{2}γ(G, k).

On the other hand, an ⟨m⟩ quasi-coloring for H implies an ⟨⌊m/s^{2}⌋⟩

Prove Lemma 7-4

quasi-coloring for G. By Lemma 8, we can assume without loss of generality that we are given a normalized ⟨m⟩ quasi-coloring, say c_{H}, of H. Construct a coloring c_{G} for G by assigning each vertex u the same color as assigned to each of its copies in H by the coloring c_{H}. By our construction of the graph H, it is easy to see that each monochromatic edge in G corresponds to a unique set of s^{2} monochromatic edges in H. We conclude that γ(H, k) ≤ s^{2}γ(G, k). The lemma follows.

Proof of Lemma 7 □

Hence we have the following theorem.

4-5

Theorem 2 For every fixed ϵ > 0 and every (2 − ϵ) < α ≤ 2, it is NP-hard to approximate γ(·, k) within O(n^{2−ϵ}) over graphs with Θ(n^{α}) edges.

Proof of Theorem 2 Lemma 6 shows that it is NP-hard to distinguish

Prove Theorem 2-1

between γ(G, k) = 0 and γ(G, k) ≥ 1, even when we are restricted to a family of graphs with Θ(n^{α}) edges where 0 < α ≤ 2.

To show the desired result, we start with the family of graphs with

Prove Theorem 2-2

Θ(n^{α+(α−2)(2−ϵ)/ϵ}) edges. Given a graph G in this family, we construct the graph H using the Amplification lemma, where we choose s = n^{\frac{2}{ϵ} −1}. Clearly, γ(H, k) is 0 if and only if γ(G, k) = 0, and γ(H, k) is Ω(N^{2−ϵ}) otherwise, where N is the number of vertices in H. This completes the proof.

Proof of Theorem 2 □

Remark 2 In fact, we can show that it is NP-hard to approximate Min k-Partition within O(n^{2−ϵ}), even when restricting the problem to dense graphs with |E| = δn^{2} for any δ < (1 − 1/k)/2. This is a sharp bound, since if δ > (1−1/k)/2, the graph cannot be k-colorable (according to Turán’s theorem), and the whole graph is trivially a 1 + 2δ/(1 − 1/k)-approximation.

The following lemma shows that the hardness result established above is

4-6

almost tight when k = 3.

Kann et al. Hardness of Approximating Max k-Cut (Ref)

14 Lemma 9 γ(G, 3) can be approximated within ϵn^{2} for every fixed ϵ > 0.

Proof of Lemma 9 Let p = 1/ϵ. If γ(G, 3) > p, then the set of all edges

Prove Lemma 9-1

constitutes a sufficiently good solution (as discussed in Section 2, we take max(γ(G, 3), 1) to compute the performance ratio). So we assume that γ(G, 3) ≤ p. Delete from G all vertices of degree at most (ϵ/2)n. We delete at most (ϵ/2)n^{2} edges in this process. Now we are left with a graph G′ that satisfies the property that each vertex has degree at least (ϵ/2)n. In G′, for every subset of at most p edges, we test whether the graph obtained by deleting F from G′ is 3-colorable. Assuming that n is large enough, the resulting graph is still ϵ′-dense for some ϵ′ < ϵ. Hence if the resulting graph is 3-colorable, we can indeed verify so by using the coloring algorithm of Edwards [Edw86] or Arora et al. [AKK95]. The result follows.

Proof of Lemma 9 □

Petrank showed in [Pet94] that for graphs with Θ(n) edges, it is NP-hard

4-7

to approximate γ(H, k) to within a factor of O(|E(H)|) (whenever k ≥ 3). We can use the Amplification lemma to strengthen this result and obtain the following.

Theorem 3 For each k > 2 and 0 < ϵ < 1, it is NP-hard to approximate γ(H, k) within O(|E(H)|) over the graphs with Ω(n^{2−ϵ}) edges.

Proof of Theorem 3 Petrank showed in [Pet94] the following. For each

Prove Theorem 3-1

k ≥ 3, there is some constant c such that it is NP-hard to tell whether a given graph G, from a family F of graphs with Θ(n) = c′n edges, satisfies γ(G, k) = 0 or γ(G, k) ≥ cn. Applying the Amplification lemma with s = n^{(1−ϵ)/ϵ} to a graph G of F gives a graph H such that: |V (H)| = sn, |E(H)| = c′s^{2}n, γ(G, k) = 0 if and only if γ(H, k) = 0, and γ(G, k) ≥ cn if and only if γ(H, k) ≥ s^{2}cn. That is, it is NP-hard to approximate γ(H, k) within O(|E(H)|). Since sn = n^{1/ϵ} and c′s^{2}n = c′n^{(2−ϵ)/ϵ}, the result follows.

Proof of Theorem 3 □

5 Acknowledgments

We thank Naveen Garg and Johan Håstad for several useful discussions.

5-1

15 Acknowledgement of support: Viggo Kann and Jens Lagergren were supported by grants from the Swedish Natural Science Research Council (NFR) and the Swedish Research Council for Engineering Sciences (TFR). Alessandro Panconesi was supported by a postdoctoral fellowship from the European Research Consortium in Informatics and Mathematics (ERCIM) and by an Alexander von Humboldt research fellowship and by the Swedish Institute of Computer Science. He enjoyed the hospitality of the Swedish Institute of Computer Science and the Royal Institute of Technology (KTH) in Stockholm while performing the research reported in this article.

References

[AKK95] S. Arora, D. Karger, and M. Karpinski. Polynomial time approximation schemes for dense instances of NP-hard problems. In Proceedings of the 27th Annual ACM Symposium on Theory of Computing, pages 284–293. ACM, 1995.

[BGS95] M. Bellare, O. Goldreich, and M. Sudan. Free bits, PCPs and nonapproximability—towards tight results. In Proceedings of the 36th Annual IEEE Symposium on Foundations of Computer Science, pages 422–431. IEEE, 1995.

[CK95] P. Crescenzi and V. Kann. A compendium of NP optimization problems. Technical Report SI/RR-95/02, Dipartimento di Scienze dell’Informazione, Università di Roma “La Sapienza”, 1995. The list is updated continuously. The latest version is avail-

          able at http://www.nada.kth.se/theory/problemlist.html.

[CKST95] P. Crescenzi, V. Kann, R. Silvestri, and L. Trevisan. Structure in approximation classes. In Proceedings of the 1st Annual International Conference on Computing and Combinatorics, volume 959 of Lecture Notes in Computer Science, pages 539–548. Springer-Verlag, 1995.

[CST95] P. Crescenzi, R. Silvestri, and L. Trevisan. To weight or not to weight: Where is the question? In Proceedings of the 4th Israel Symposium on Theory of Computing and Systems, pages 66–77. IEEE, 1995.

16 [Edw86] K. Edwards. The complexity of colouring problems. Theoretical

Computer Science, 43:337–343, 1986.

[FJ95] A. Frieze and M. Jerrum. Improved approximation algorithms for MAX k-CUT and MAX BISECTION. In Proceedings of the 4th International Conference on Integer Programming and Combinatorial Optimization, volume 920 of Lecture Notes in Computer Science, pages 1–13. Springer-Verlag, 1995.

[GVY96] N. Garg, V. V. Vazirani, and M. Yannakakis. Approximate maxflow min-(multi)cut theorems and their applications. SIAM Journal on Computing, 25:235–251, 1996.

[GW95] M. X. Goemans and D. P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM, 42:1115–1145, 1995.

[Hås97] J. Håstad. Some optimal inapproximability results. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing, pages 1–10. ACM, 1997.

[MR95] R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995.

[Pet94] E. Petrank. The hardness of approximation: Gap location. Computational Complexity, 4:133–157, 1994.

[PT95] S. Poljak and Z. Tuza. Maximum cuts and largest bipartite subgraphs. In W. Cook, L. Lovász, and P. Seymour, editors, Combinatorial Optimization, volume 20 of DIMACS: Series in Discrete Mathematics and Theoretical Computer Science. American Mathematical Society, 1995.

[PY91] C. H. Papadimitriou and M. Yannakakis. Optimization, approximation, and complexity classes. Journal of Computing and System Sciences, 43:425–440, 1991.

[Tur41] P. Turán. An extremal problem in graph theory. Matematikai Fizikai Lapok, 48:436–452, 1941. Written in Hungarian.

17 Kann et al. Hardness of Approximating Max k-Cut (Ref)

[Wes96] D. B. West. Introduction to Graph Theory. Prentice-Hall Inc., NJ, 1996.