Bilu-Linial Stable Instances of Max Cut and Minimum Multiway Cut

Introduction

Empirical evidence suggests that many discrete optimization problems like clustering and partitioning are much easier in practice than in the worst case. Even though these problems are usually provably hard in the worst case, we can still try to design algorithms that work well on instances that we encounter in practice. To do so, we need a good mathematical model for such instances.

There are several approaches to modeling real-life instances. Perhaps, a more classical approach dating back to early 1980’s is to assume that real-life instances come from a random or “semi-random” distribution . To learn more about this approach, we refer the interested reader to our previous work on semi-random instances of graph partitioning and references therein. An alternative approach, which we study here, is to identify certain structural properties that “interesting” instances (or “practically interesting instances” ) must satisfy, and then assume that instances arising in practice satisfy them. One such property was proposed by Bilu and Linial .

Bilu and Linial introduced a notion of stability of instances for discrete optimization problems. They argue that interesting instances have stable solutions: the optimal solution does not change upon small perturbations. For example, a clustering instance that is meaningful should have a solution that stands out. This solution should remain optimal even if the edge weights are slightly inaccurate or noisy. As Balcan, Blum and Gupta argue, the real goal of solving a clustering problem is often to obtain the correct “target” clustering, and so the objective function serves only as a proxy. In this case, if the edge weights, which may be rough estimates of how similar or dissimilar the endpoints are, are imprecise, then the solution is meaningful only when the instance is stable. Here is a formal definition of $\gamma$-stability .

Consider an instance of a graph optimization problem on $n$ vertices, defined by the matrix of non-negative edge weights $w$. We say that the instance is $\gamma$-stable if there is an optimal solution which remains optimal, even when any subset of the edge weights are increased by a factor of at most $\gamma$.

We note that prior to work of Bilu and Linial , Balcan, Blum and Gupta introduced and studied a somewhat similar but different notion of approximation–stability for clustering problems like $k$-means and $k$-median; later Awasthi, Blum and Sheffet , Balcan and Liang , and Reyzin studied a related notion of perturbation resilience for these center–based clustering problems.

We study stable instances of Max Cut and Minimum Multiway Cut, and propose a general technique for solving stable instances of graph partitioning problems (see Section 7). However, to be more specific, we focus our exposition on Max Cut — the problem that was previously studied by Bilu and Linial and Bilu, Daniely, Linial, and Saks . In Max Cut, we are given a weighted graph $G(V,E,w)$ on $n$ vertices with an adjacency matrix $w$. Our goal is to find a cut $(S,V\setminus S)$ in the graph with the maximum weight of edges crossing it

Max Cut is one of the classic NP-hard problems . It is NP-hard to approximate within a factor of $17/16$ . Goemans and Williamson gave a semidefinite programming based algorithm that achieves a $0.878$ approximation ratio for Max Cut. Khot, Kindler, Mossel and O’Donnell showed that this is the best possible approximation ratio in the worst-case, assuming the Unique Games Conjecture .

In the work that introduced $\gamma$-stability, Bilu and Linial designed an algorithm for $\gamma$-stable instances of Max Cut with $\gamma\geq cn$ (for some absolute constant $c$). The aim of the algorithm is to find the exact optimal solution. This solution is unique (because of stability) and corresponds to the “true” partitioning we want to find. Finding just a good approximation for $\gamma$-stable instances of Max Cut is easy, since $\gamma$-stable instances of Max Cut are almost bipartite, and for almost bipartite graphs, the algorithm of Goemans and Williamson returns a solution in which almost all edges are cut (see for more details). Bilu, Daniely, Linial, and Saks gave an algorithm for $\gamma$-stable Max Cut instances with $\gamma\geq c\sqrt{n}$ (for some absolute constant $c$). Both papers also gave better algorithms for stable instances that satisfy some extra conditions (see and ).

In this work, we give an algorithm that solves $\gamma$-stable instances of Max Cut with $\gamma\geq c\sqrt{\log n}\log\log n$ (for some absolute constant $c$). We also study the classic partitioning problem of finding the Minimum Multiway Cut (see Section 4 for the definition) and give an algorithm for $\gamma$-stable instances of it, with $\gamma\geq 4$. Our result for Max Cut is an exponential improvement over previous results. Our algorithms are robust (in the notion of Raghavan and Spinrad ):

If the instance is $\gamma$-stable, the algorithm finds the unique optimal solution.

If the instance is not $\gamma$-stable, the algorithm either finds an optimal solution, or a (polynomial-time verifiable) certificate that proves that the instance is not $\gamma$-stable.

In other words, our algorithm is always correct: when we claim to output the maximum cut (minimum multiway cut), we can guarantee its optimality; else we identify that the given graph is not sufficiently stable. This is a very desirable property for algorithms we want to use in practice, since we may only assume that real-life or important instances are stable (or satisfy other properties), but we cannot be completely certain that they indeed are. When we use robust algorithms, we cannot get a suboptimal solution even if our assumptions are not quite correct. Note that previous algorithms for stable instances of Max Cut , and Clustering are not robust. That is, if the instance is not $\gamma$-stable, the previous algorithms can output a suboptimal solution without notifying us that the solution is suboptimal.

Our algorithms use that our SDP and LP relaxations for Max Cut and Minimum Multiway Cut, respectively, are integral when $\gamma$ is sufficiently large. For Max Cut, we prove that the standard SDP relaxation with triangle inequalities is integral for $(c\sqrt{\log n}\log\log n)$-stable instances. We remark that we are unaware of other natural settings when the semidefinite program becomes integral and the corresponding linear program does not!

We also present algorithms that work for the same values of $\gamma$ with a more relaxed notion of stability which we call weak stability. The optimal solution of every perturbed instance of a weakly stable instance, is close to the optimal solution of the original instance, but may not be exactly the same (see Section 6 for details). We believe that $\gamma$-weak stability may be a more realistic assumption than $\gamma$-stability in practice. Bilu and Linial mentioned weakly stable instances in the introduction to their paper (without formally defining them), and proposed to study them in the future. Our algorithms for $\gamma$-weakly stable instances are not robust.

Our result for weakly stable instances of Max Cut uses an approximation algorithm for Sparsest Cut with non-uniform demands as a black box. In particular, the result implies that if there is an $\alpha(n)$-approximation algorithm for Sparsest Cut (which finds approximately not only the value but also a solution to Sparsest Cut) then there is an exact algorithm for $(1+\varepsilon)\alpha(n)$-stable instances of Max Cut. (For simplicity of exposition, $\varepsilon$ is fixed in our proof; in general, $\varepsilon$ can be sub-constant, the running time is proportional to $1/\varepsilon$.)

Finally, we present a general approach to solving stable instances of graph partitioning problems.

Negative Results.

We note that our positive results for Max Cut also apply to the problem of clustering points into two clusters (or, equivalently, to Max Cut with positive and negative weights). Our negative result for Max $k$-Cut, on the other hand, shows that there is no exact algorithm for the problem of clustering points into $k$ clusters when $k\geq 3$ unless $RP=NP$ (see Appendix B for details).

1 Overview of Techniques

Our algorithm for weakly stable instances starts with an approximate solution and then iteratively improves the quality of the solution using the algorithm for non-uniform Sparsest Cut by Arora, Lee, and Naor as a subroutine.

2 Outline

In Section 2, we introduce the formal definitions of stability and some preliminaries including the semidefinite program (SDP) we use in our algorithm. Then, in Section 3, we describe our robust algorithm for $\gamma$-stable instances of Max Cut. In Section 5, we present evidence suggesting that obtaining algorithms for better values of $\gamma$ may not be easy. We first give a reduction from non-uniform Sparsest Cut (in Section 5.2), which shows that any robust algorithm with better guarantees would lead to a similar improvement for non-uniform Sparsest Cut. Then we show in Section 5.3 that the SDP is not integral for smaller values of $\gamma$. In Section 4, we present our algorithm for $4$-stable instances of Minimum Multiway Cut. In Section 6, we introduce a more general notion of weak stability and obtain similar guarantees in this setting.

We describe our results for Max $k$-Cut and Correlation Clustering in Sections 5.4 and Appendix B, respectively. Finally, we outline a general approach for solving stable instances of graph partitioning problems in Section 7.

Preliminaries

We start with formally defining the notion of Bilu–Linial stability for Max Cut instances. Following , we give two equivalent definitions (see Proposition 2.1 in ).

Let $G=(V,E,w)$ be a weighted graph with edge weights $w(e)$ and let $\gamma>1$. A weighted graph $G^{\prime}=(V,E,w^{\prime})$ is a $\gamma$-perturbation of $G$ if for every $(u,v)\in V$,

We say that $G$ is a $\gamma$-stable instance of Max Cut if there is a unique cut which forms a maximal cut for every $\gamma$-perturbation $G^{\prime}$ of $G$.

Let $\gamma\geq 1$. A weighted graph $G$ graph with maximal cut $(S,\bar{S})$ is $\gamma$-stable instance of Max Cut if for every vertex set $T\neq S$ and $T\neq\bar{S}$:

We show that $\gamma$-stable instances of Max Cut are integral. The formal definition of an integral SDP is as follows.

Let $G$ be an instance of Max Cut. We say that an SDP solution $\{\bar{u}\}$ is integral if there exists a vector $\bar{e}$ such that $\bar{u}=\bar{e}$ or $\bar{u}=-\bar{e}$ for every $u\in V$. We say that the SDP relaxation for $G$ is integral if every optimal SDP solution for $G$ is integral.

Our algorithm for $\gamma$-stable instances is robust in the sense of Raghavan and Spinrad : it always returns a correct output regardless of whether the input is $\gamma$-stable or not.

An algorithm for $\gamma$-stable instances of Max Cut is robust if the following conditions hold.

If the input instance is $\gamma$-stable, the algorithm must output a maximum cut.

If the input instance is not $\gamma$-stable, the algorithm must either output a maximum cut or a special symbol $\perp$ (which certifies that the instance is not $\gamma$-stable).

In the proof, we use some standard definitions from metric geometry.

The Lipschitz constant $\|\varphi\|_{Lip}$ of a map $\varphi$ between two metric spaces $(X,d_{X})$ and $(Y,d_{Y})$ equals

The distortion of an embedding $\varphi:X\hookrightarrow Y$ equals $\|\varphi\|_{Lip}\cdot\|\varphi^{-1}\|_{Lip}$ (the distortion is infinite if $\varphi$ is not injective).

Now recall the definition the Sparsest Cut problem with non-uniform demands.

We denote the best possible approximation factor for the problem by $\alpha_{SC}(n)$. Strictly speaking, $\alpha_{SC}(n)$ is not well-defined. Formally, we consider the decision version of the problem: the approximation algorithm has to output only the approximate value of the problem. We write $\alpha_{SC}(n)\leq f(n)$ if there is an algorithm with approximation guarantee $f(n)$; we write $\alpha_{SC}(n)>f(n)$ if there is no algorithm with approximation guarantee $f(n)$. However, the algorithm of Arora, Lee, and Naor that we use in this paper not only finds the approximate value but also finds the corresponding solution.

Algorithm for Max Cut

Let $(S,\bar{S})$ be the maximum cut in $G$. Since $\{\bar{u}\}$ is an optimal SDP solution, we have that its SDP value is at least the cost of the maximum cut:

Note that not all vectors $\hat{u}$ are equal since the SDP solution is not integral. If $(u,v)\in E(S,\bar{S})$ then

if $(u,v)\in E\setminus E(S,\bar{S})$ then $\|\bar{u}-\bar{v}\|^{2}=\|\hat{u}-\hat{v}\|^{2}$. Therefore,

Here, we use that not all vectors in $X$ are equal and therefore cuts in the distribution are not trivial. Let $A^{\prime}=\{u:\hat{u}\in A\}$ and $\bar{A}^{\prime}=V\setminus A^{\prime}=\{u:\hat{u}\notin A\}$. We get,

In particular, for some cut $A^{\prime\prime}$, we have

Let $T=(S\cap A^{\prime\prime})\cup(\bar{S}\cap\bar{A}^{\prime\prime})$ (see Figure 1). Note that $A^{\prime\prime}\neq V$ and $A^{\prime\prime}\neq\varnothing$, hence $T\neq S$ and $T\neq\bar{S}$. Write

which contradicts to the fact that $G$ is a $\gamma$-stable instance (see Definition 2.2). ∎

From Theorem 3.1, we get the main algorithmic result of our paper.

The algorithm solves the SDP relaxation for the problem. If the solution is integral, the algorithm returns the cut corresponding to it. Otherwise, it returns $\perp$ (indicating that the instance is not $\gamma$-stable). Note that if the algorithm returns a cut, it must be a maximum cut (otherwise, the SDP solution would not be optimal). By Theorem 3.1, the algorithm always returns a solution if the instance is $\gamma$-stable. ∎

Algorithm for Minimum Multiway Cut

In this section, we study stable instances of Minimum Multiway Cut. We prove that the linear programming relaxation of Călinescu, Karloff, and Rabani is integral for $4$-stable instances of the problem. Thus there is a robust polynomial-time algorithm for 4-stable instances of Minimum Multiway Cut.

The Minimum Multiway Cut problem was introduced by Dahlhaus, Johnson, Papadimitriou, Seymour, and Yannakakis . We refer the reader to for the summary of known results for the problem.

In the Minimum Multiway Cut problem, we are given a graph $G=(V,E,w)$ with positive edge weights $w_{e}$ and a set of terminals $T=\{s_{1},\dots,s_{k}\}\subset V$. Our goal is to partition the graph into $k$ pieces $S_{1},\dots,S_{k}$ such that $s_{i}\in S_{i}$ so as to minimize the total weight of cut edges.

We give a definition of $\gamma$-stable instances of Minimum Multiway Cut (cf. Definition 2.1).

Let $\gamma>1$. An instance $\{G=(V,E,w),T\}$ of Minimum Multiway Cut is $\gamma$-stable if there is a multiway cut ${\cal S}$ which is the unique optimal solution for every $\gamma$-perturbation of $G$.

We also restate this definition as follows (cf. Definition 2.2).

Consider an instance $\{G=(V,E,w),\,T\}$ of Minimum Multiway Cut. Let $\gamma>1$. Denote the optimal multiway cut by ${\cal S}^{*}$, and let the set it cuts be $E^{*}$. We say that $G$ is a $\gamma$-stable instance of Multiway Cut if for every multiway cut ${\cal S}^{\prime}\neq{\cal S}^{*}$, we have

where $E^{\prime}$ is the set of edges cut by ${\cal S}^{\prime}$.

Every feasible LP solution defines a metric on $V$: $d(u,v)=\|\bar{u}-\bar{v}\|_{1}/2$. We will need the following lemma.

Consider a feasible LP solution $\{\bar{u}:u\in V\}$. There is a distribution of multiway cuts (partitions) $S_{1},\dots,S_{k}$ such that

$s_{i}\in S_{i}$ for every $i\in\{1,\dots,k\}$ (always),

$\Pr(u\text{ and }v\text{ are separated by the cut})\leq\frac{2d(u,v)}{1+d(u,v)}$ for every $u$ and $v$ ($u$ and $v$ are separated if $u\in S_{i}$ and $v\in S_{j}$ with $i\neq j$). In particular, for every edge $(u,v)$ (see Figure 2),

If the LP solution is not integral, the distribution is supported on at least two multiway cuts.

We use the rounding scheme of Kleinberg and Tardos (which they used in their algorithm for the Metric Labeling problem) to round the LP solution to an integral solution. The scheme works as follows. We iteratively construct sets $S_{1},\dots,S_{k}$. We start with empty sets $S_{1},\dots,S_{k}$ and then in each iteration add vertices to one of the sets $S_{1},\dots,S_{k}$. We stop once each vertex $u$ belongs to some set $u$. In each iteration, we choose independently and uniformly at random $r\in(0,1)$ and $i\in\{1,\dots,k\}$. We add each vertex $u$ to $S_{i}$ if $r\leq\bar{u}_{i}$ and it was not added to any set $S_{j}$ in previous iterations.

First, note that we add every vertex $u$ to some $S_{i}$ with probability $\sum_{i=1}^{k}\bar{u}_{i}/k=1/k$ in each iteration (unless $u$ already lies in some $S_{j}$). So eventually we will add every vertex to some set $S_{i}$. Also note that we cannot add $s_{i}$ to $S_{j}$ if $j\neq i$. Therefore, $s_{i}\in S_{i}$.

Now consider two vertices $u$ and $v$. Consider an iteration of our partitioning algorithm. Suppose that neither $u$ nor $v$ is assigned to some $S_{j}$. The probability that at least one of them is assigned to some $S_{i}$ in this iteration is

The probability that exactly one of them is assigned to some $S_{i}$ is

Therefore, the probability that $u$ and $v$ are separated in some iteration is $2d(u,v)/(1+d(u,v))$. The probability that $u$ and $v$ belong to different pieces of the cut is at most $2d(u,v)/(1+d(u,v))$.

Finally, note that if some $\bar{u}_{j}\in(0,1)$ then with positive probability $u\in S_{j}$, and with positive probability $u\notin S_{j}$. Therefore, if the LP solution is not integral, the distribution of multiway cuts is supported on at least two multiway cuts. ∎

Note that in general this rounding scheme gives only a $2$ approximation for Multiway Cut. Other known rounding schemes achieve a better approximation; e.g. the rounding scheme of Călinescu, Karloff, and Rabani gives a $3/2$ approximation. However, this rounding scheme has a property that other rounding schemes do not have: it does not cut an edge $(u,v)$ with probability at least $(1-d(u,v))/{2}=\Omega(1-d(u,v))$. This property is crucial for our proof (we discuss why this property is important in Section 7).

Now we prove the main result of this section.

The LP relaxation is integral if the instance is $4$-stable.

We conclude that $\mathsf{LP}_{+}<\mathsf{LP}_{-}$. On the other hand,

since the value of the relaxation is at most the value of the integral solution. We get a contradiction. ∎

As an immediate corollary we get that there is a robust polynomial-time algorithm for $4$-stable instances of Multiway Cut.

There is a robust polynomial-time algorithm for $4$-stable instances of Multiway Cut.

We solve the LP relaxation for Multiway Cut. If the LP solution is integral, we return the corresponding combinatorial solution. Otherwise, we return that the instance is not $4$-stable. ∎

Negative Results

We first present a reduction from Sparsest Cut to Max Cut, which we use later to prove both our negative results.

Let $S=\left\{u_{1}:u\in V_{0}\right\}$ and $\bar{S}=V\setminus S=\left\{u_{2}:u\in V_{0}\right\}$.

If $\phi(A)>\gamma$ for every cut $(A,\bar{A})$ (see Definition 2.8), then the instance $G$ is $\gamma$-stable with the maximum cut $(S,\bar{S})$.

We need to show that for every cut $(T,\bar{T})$ different from $(S,\bar{S})$:

Here, we use Definition 2.2 of $\gamma$-stability. Note that if for some $u$, the edge $(u_{1},u_{2})$ is not cut by $E(T,\bar{T})$ then $w(E(S,\bar{S})\setminus E(T,\bar{T}))\geq w(u_{1},u_{2})=W_{\infty}$ and $\gamma\cdot w(E(T,\bar{T})\setminus E(S,\bar{S}))<W_{\infty}$, and the desired inequality holds. So we assume below that every edge $(u_{1},u_{2})$ is cut by $E(T,\bar{T})$. Then, for every $u$ either $u_{1}\in T$ and $u_{2}\in\bar{T}$, or $u_{1}\in\bar{T}$ and $u_{2}\in T$. Let

Observe, that $S\cap T=\{u_{1}:u\in A\}$; $S\cap\bar{T}=\{u_{1}:u\in\bar{A}\}$, similarly $\bar{S}\cap T=\{u_{2}:u\in\bar{A}\}$; $\bar{S}\cap\bar{T}=\{u_{2}:u\in A\}$. Since $\phi(A)>\gamma$, we have

as required. We proved that the instance is $\gamma$-stable. ∎

2 Hardness Result for Max Cut

We now prove that there is no robust polynomial-time algorithm for $\gamma$-stable instances of Max Cut when $\gamma<\alpha_{SC}(n/2)$.

Suppose that there is a robust polynomial-time algorithm $\cal A$ for $\gamma$-stable instances of Max Cut with $\gamma\geq\gamma(n)$. Then there is a polynomial-time algorithm $\cal B$ for the decision version of Sparsest Cut with promise that either

The algorithm given a Sparsest Cut instance decides whether $\phi^{*}<\phi_{0}$ or $\phi^{*}>\gamma(2n)\phi_{0}$.

We may assume that $\phi_{0}=1$ by dividing all edge weights by $\phi_{0}$. We apply reduction from Section 5.1 and obtain a graph $G$ on $2n$ vertices. Then we run $\cal A$ on $G$. If $\cal A$ returns the cut $(S,\bar{S})$ (where $S=\{u_{1}:u\in V_{0}\}$), we decide that $\phi^{*}>\gamma(2n)$. Otherwise, we decide that $\phi^{*}<1$.

We prove that we always decide correctly. Assume first that $\phi^{*}>\gamma(2n)$ then $G$ is $\gamma(2n)$-stable and $(S,\bar{S})$ is the maximum cut by Lemma 5.1. Therefore, $\cal A$ returns $(S,\bar{S})$ and we correctly decide that $\phi^{*}>\gamma(2n)$. Now assume that $\phi^{*}<1$. Denote the sparsest cut in $G$ by $A$. Let $T=\left\{u_{1}:u\in A\right\}\cup\left\{u_{2}:u\notin A\right\}$. We have,

Hence $(S,\bar{S})$ is not a maximum cut. Since $\cal A$ is a robust algorithm it must either return a cut different from $(S,\bar{S})$ or $\perp$. Therefore, we decide that $\phi^{*}>\gamma(2n)$.

We get as a corollary that if there is a robust polynomial-time algorithm for $\gamma$-stable instances of Max Cut then there is a $\gamma(2n)$-approximation algorithm for Sparsest Cut (the algorithm finds the value of Sparsest Cut but not the actual cut).

Suppose that there is a robust polynomial-time algorithm $\cal A$ for $\gamma$-stable instances of Max Cut with $\gamma\geq\gamma(n)$. Then there is a polynomial-time algorithm for the decision version of Sparsest Cut that given an instance with value $\phi^{*}$ and $\varepsilon>0$ outputs a value $\phi_{\text{approx}}$ between $(1-\varepsilon)\phi^{*}/\gamma(2n)$ and $\phi^{*}$.

Let $\phi_{ARV}$ be the approximate value of the problem given by the algorithm of Arora, Rao and Vazirani. We try all possible values of $\phi_{0}$ of the form $(1+k\varepsilon)\phi_{ARV}$ in the range $(\phi_{ARV},(\alpha_{ARV}+\varepsilon)\phi_{ARV})$. For each value, we run the algorithm $\cal B$ from Theorem 5.2. We find the smallest value $\phi_{\text{approx}}^{\prime}$ of $\phi_{0}$ such that $\cal B$ returns that $\phi^{*}<\phi_{0}$. Note that if $\phi_{0}>\phi^{*}$ then the promise of Theorem 5.2 is satisfied and thus the algorithm $\cal B$ returns that $\phi^{*}<\phi_{0}$. Therefore, $\phi_{\text{approx}}^{\prime}\leq(1+\varepsilon)\phi^{*}$.

Similarly, if $\phi_{0}<\phi_{*}/\gamma(2n)$ then the promise is satisfied and thus $\cal B$ returns that $\phi_{*}>\gamma(2n)\phi_{0}$. Therefore, $\phi_{\text{approx}}^{\prime}\geq\phi^{*}/\gamma(2n)$. We output $\phi_{\text{approx}}=\phi_{\text{approx}}^{\prime}/(1+\varepsilon)$. ∎

We note that Theorem 5.2 implies that there is no polynomially-time tractable relaxation for Max Cut that is integral on $\gamma$-stable instances if $\gamma<\alpha_{SC}(n/2)$. If there was such a relaxation, by solving it, we would get a robust algorithm as we do in Corollary 3.2.

There is no polynomial-time tractable relaxation for Max Cut that is integral on $\gamma$-stable instances if $\gamma<\alpha_{SC}(n/2)$.

3 SDP Integrality Gap

We will need the following technical lemma.

To prove the lemma, we first rescale demands so that conditions (5) and (6) hold. Then we transform vectors $u$ so that all of them lie on the unit sphere. Specifically, if all vectors $u_{i}$ lie on some sphere, we scale all vectors $u_{i}$ to unit vectors and move the origin to the center of the sphere; these transformations preserve ratios of distances between vectors. In a degenerate case, when all vectors $u_{i}$ do not lie on a sphere, we first slightly perturb all vectors and then apply the above argument. The formal proof is a bit technical, so we present it in Appendix A.

Using that $\|\bar{u}+\bar{v}\|^{2}=4-\|\bar{u}-\bar{v}\|^{2}$, we get

We conclude that the optimal SDP solution has value at least $SDP$, which is greater than $w(S,\bar{S})$. Therefore, the SDP relaxation is not integral.

4 Hardness Result for Max k𝑘k-Cut

In this section, we prove a hardness result for Max $k$-Cut.

The Max $k$-Cut problem is to partition a given weighted graph $G$ into $k$ pieces so as to maximize the total weight of cut edges.

Let us say that an instance $G=(V,E,w)$ of Max $k$-Cut is $\infty$-stable if it is $\gamma$-stable for every $\gamma$. That is, there is a partition $\cal P$ of $V$ such that for every set of positive weights $w^{\prime}$, $\cal P$ is an optimal solution for Max Cut instance $G^{\prime}=(V,E,w^{\prime})$.

For every $k\geq 3$, there is no polynomial-time algorithm that solves $\infty$-stable instances of Max $k$-Cut unless $NP=RP$.

The claim easily follows from the hardness result for the Unique $k$-Coloring problem by Barbanchon . Recall that a graph $G$ is uniquely $k$ colorable if there exists exactly one proper coloring of $G$ in $k$ colors (up to permutation of the colors). Barbanchon showedBarbanchon states his result only for $k=3$. The result for $k>3$ follows from his result as follows. For a graph $G$, let $G^{\prime}$ be the union of graphs $G$ and $K_{k-3}$ in which every vertex of $G$ is connected with every vertex of $K_{k-3}$. Then $G$ is uniquely 3-colorable if and only if $G^{\prime}$ is uniquely $k$-colorable. that there is no polynomial algorithm that given a uniquely $k$-colorable graph finds its $k$ coloring unless $NP=RP$.

Let $G$ be a uniquely $k$-colorable graph. We assign each edge of $G$ weight $1$ and obtain an instance of Max $k$-Cut. We show that the instance is $\infty$-stable. Let $\cal P$ be the partition corresponding to the unique $k$-coloring $\cal C$ of $G$. Note that no matter what positive weights we assign to edges, the value of $\cal P$ equals the total weight of all edges in the graph (since $\cal P$ cuts all edges). Thus $\cal P$ is an optimal $k$-partition. Moreover, $\cal P$ is the only optimal partition. Indeed if a $k$-partition ${\cal P}^{\prime}$ cuts all edges, then the coloring that colors every piece in ${\cal P}^{\prime}$ in its own color is a proper $k$-coloring, and thus it is equal to $\cal C$ (up to permutation of the colors). The result of Barbanchon implies that there is no polynomial-time algorithm that finds the optimal Max $k$-Cut in $G$ unless $NP=RP$. ∎

Weakly Stable Instances

In this section, we define a relaxed notion of stability, which we call weak stability, and give an algorithm for approximately solving weakly stable instances of Max Cut. We note that Awasthi, Blum and Sheffet and Balcan and Liang studied a very closely related notion of perturbation resilience for the $k$-Median Clustering problem.

Consider a weighted graph $G=(V,E,w)$. Let $(S,\bar{S})$ be a maximum cut in $G$, $N$ be a set of cuts that contains $(S,\bar{S})$, and $\gamma\geq 1$. We say that $G$ is a $(\gamma,N)$-weakly stable instance of Max Cut if for every $\gamma$-perturbation $G^{\prime}=(V,E,w^{\prime})$ of $G$, we have

This definition is equivalent to the following definition (see Appendix C for the proof).

Consider a weighted graph $G=(V,E,w)$. Let $(S,\bar{S})$ be a maximum cut in $G$, $N$ be a set of cuts that contains $(S,\bar{S})$, and $\gamma\geq 1$. We say that $G$ is a $(\gamma,N)$-weakly stable instance of Max Cut if for every cut $(T,\bar{T})\notin N$:

The notion of weak stability generalizes the notion of stability: an instance is $\gamma$-stable if and only if it is $(\gamma,\left\{(S,\bar{S})\right\})$-weakly stable. We think of the set $N$ in the definition of weak stability as a neighborhood of the maximum cut $(S,\bar{S})$; it contains cuts that are “close enough” to $(S,\bar{S})$. Intuitively, the definition requires that every cut that is sufficiently different from $(S,\bar{S})$ is much smaller then $(S,\bar{S})$, but does not impose any restrictions on cuts that are close to $(S,\bar{S})$. One natural way to define the neighborhood of $(S,\bar{S})$ is captured in the following definition.

Consider a weighted graph $G$. Let $(S,\bar{S})$ be a maximum cut in $G$, $\delta\geq 0$, and $\gamma\geq 1$. We say that $G$ is a $(\gamma,\delta)$-weakly stable instance of Max Cut if $G$ is $(\gamma,\left\{(S^{\prime},\bar{S}^{\prime}):|S\Delta S^{\prime}|\leq\delta n\right\})$-weakly stable. In other words, $G$ is $(\gamma,\delta)$-weakly stable if for every cut $(T,\bar{T})$ such that $|S\Delta T|>\delta n$ and $|S\Delta{\bar{T}}|>\delta n$, we have

The main result of this section is the following theorem.

There is a polynomial-time algorithm that given a $(\gamma,N)$-stable instance of Max Cut, returns a cut from $N$ if $\gamma\geq c\sqrt{\log n}\log\log n$ (for some absolute constant $c$). (The set $N$ is not part of the input and is not known to the algorithm.)

The algorithm starts with an arbitrary cut and then iteratively improves it. We now describe a subroutine that algorithm runs in each iteration.

We construct an auxiliary Sparsest Cut instance $\cal I$ on $V$ defined by

Then we run the approximation algorithm for Sparsest Cut by Arora, Lee and Naor and find an approximate cut $(A,\bar{A})$. We let $T^{\prime}=(T\cap A)\cup(\bar{T}\cap\bar{A})$ (see Figure 3). If $w(T^{\prime},\bar{T}^{\prime})\geq w(T,\bar{T})+\omega$ then we return $(T^{\prime},\bar{T}^{\prime})$, otherwise we return $\perp$.

Whenever the algorithm returns a cut, the cut satisfies the requirement $w(T^{\prime},\bar{T}^{\prime})\geq w(T,\bar{T})+\omega$. Thus we only need to prove that if $w(E(S,\bar{S})\setminus E(T,\bar{T}))\geq 4m\omega$ then the algorithm finds a cut.

First we show that there is a Sparsest Cut with sparsity at most $2/\gamma$ in $\cal I$. Let $A^{*}=(S\cap T)\cup(\bar{S}\cap\bar{T})$. Since $(T,\bar{T})\notin N$, we have $w(E(S,\bar{S})\setminus E(T,\bar{T}))>\gamma\cdot w(E(T,\bar{T})\setminus E(S,\bar{S}))$, or equivalently $w((E\setminus E(T,\bar{T}))\cap E(A^{*},\bar{A}^{*}))>\gamma\cdot w(E(T,\bar{T})\cap E(A^{*},\bar{A}^{*}))$. Thus

We get that $\phi(A^{*})<2/\gamma$. Therefore, our algorithm finds a cut $A$ with $\phi(A)\leq O(\sqrt{\log n}\log\log n)\cdot 2/\gamma<1/2$. We have

Algorithm. We start with an arbitrary cut $(T,\bar{T})$. Then we iteratively run the algorithm $\cal A$ from Lemma 6.5. In each iteration, we go over all values of $\omega$ in $\Omega=\{w(u,v)/(4m):(u,v)\in E\}$ in the descending order, and execute $\cal A$ on input $G$, $(T,\bar{T})$ and $\omega$. If $\cal A$ finds a cut $(T^{\prime},\bar{T}^{\prime})$, we let $T=T^{\prime}$ and start a new iteration. If $\cal A$ does not find any cut, we stop and output $(T,\bar{T})$.

Analysis. We first show that the algorithm always returns a cut from $N$. At every step of the algorithm when $(T,\bar{T})\notin N$, we have $w(S,\bar{S})>w(T,\bar{T})$, hence $E(S,\bar{S})\setminus E(T,\bar{T})\neq\varnothing$ and $w(E(S,\bar{S})\setminus E(T,\bar{T}))\geq\min_{e\in E}w(e)$. Therefore, for some $\omega\in\Omega$ (in particular, for $\omega=\frac{\min_{e\in E}w(e)}{4m}$; see the statement of Lemma 6.5), the algorithm $\cal A$ finds a better cut $(T^{\prime},\bar{T}^{\prime})$, and the main algorithm does not terminate. It remains to check that the running time is polynomial.

Consider one iteration of the algorithm. Let $(T,\bar{T})$ be the current cut. Let $(u,v)$ be the heaviest edge in $E(S,\bar{S})\setminus E(T,\bar{T})$ and $\omega^{*}=w(u,v)/(4m)$. Note that in this iteration we find a cut when we run $\cal A$ with some $\omega\geq\omega^{*}$ (since if we do not find a cut $(T^{\prime},\bar{T}^{\prime})$ when $\omega>\omega^{*}$, we must find a cut $(T^{\prime},\bar{T}^{\prime})$ when $\omega=\omega^{*}$ by Lemma 6.5). We also have

We charge this iteration to “level” $\omega$. We show that every $\omega\in\Omega$ pays for at most $4m^{2}$ iterations and therefore the number of iterations is $O(m^{3})$.

Indeed, consider $\omega\in\Omega$. Let $T_{0}$ be the value of $T$ just before we perform an iteration at level $\omega$ for the first time, and $T_{k}$ be the value of $T$ right after we perform $k$ iterations at level $\omega$ (possibly we perform iterations at other levels in between). We have,

Since $w(E(T_{k},\bar{T}_{k}))\leq w(E(S,\bar{S}))$, we get that $k\leq 4m^{2}$. This concludes the proof. ∎

2 Weakly Stable Instances of Minimum Multiway Cut

In this section, we give an algorithm for approximately solving weakly stable instances of Minimum Multiway Cut.

Consider a weighted graph $G$. Let ${\cal S}^{*}=(S_{1}^{*},\dots,S_{k}^{*})$ be a minimum multiway cut in $G$, $N$ be a set of multiway cuts that contains ${\cal S}^{*}$, and $\gamma\geq 1$. We say that $G$ is a $(\gamma,N)$-weakly stable instance of Minimum Multiway Cut if for $\gamma$-perturbation $G^{\prime}=(V,E,w^{\prime})$ of $G$ and every multiway cut ${\cal S}^{\prime}=(S_{1}^{\prime},\dots,S_{k}^{\prime})\notin N$:

where $E^{*}$ is the set of edges cut by ${\cal S}^{*}$ and $E^{\prime}$ is the set of edges cut by ${\cal S}^{\prime}$.

This definition is equivalent to the following definition (see Appendix C for the proof).

Consider a weighted graph $G$. Let ${\cal S}^{*}=(S_{1}^{*},\dots,S_{k}^{*})$ be a minimum multiway cut in $G$, $N$ be a set of multiway cuts that contains ${\cal S}^{*}$, and $\gamma\geq 1$. We say that $G$ is a $(\gamma,N)$-weakly stable instance of Minimum Multiway Cut if for every multiway cut ${\cal S}^{\prime}=(S_{1}^{\prime},\dots,S_{k}^{\prime})\notin N$:

where $E^{*}$ is the set of edges cut by ${\cal S}^{*}$ and $E^{\prime}$ is the set of edges cut by ${\cal S}^{\prime}$.

The main result of this section is the following theorem.

There is a polynomial-time algorithm for the following task. Given a $(4,N)$-stable instance of Minimum Multiway Cut with integer edge weights in the range $[1,poly(n)]$, the algorithm returns a multiway cut from $N$. The set $N$ is not part of the input and is not known to the algorithm.

If the weights are not polynomially bounded, the following version of this theorem holds. (The proofs of Theorems 6.8 and 6.9 are very similar. For simplicity of exposition, we only present the proof of Theorem 6.8.)

There is a polynomial-time algorithm that given a $(4+\varepsilon,N)$-stable instance of Minimum Multiway Cut, returns a multiway cut from $N$. The running time of the algorithm is inversely proportional do $\varepsilon$. The set $N$ is not part of the input and is not known to the algorithm.

The algorithm starts with an arbitrary multiway cut $\cal S$ and then iteratively improves it.

There is a polynomial-time algorithm that given a $(4,N)$ weakly stable instance $G=(V,E,w)$ and a solution ${\cal S}^{\circ}$ either finds a solution ${\cal S}^{\prime}$ of smaller cost or certifies that ${\cal S}^{\circ}\in N$.

Let $E^{\circ}$ be the set of edges cut by ${\cal S}^{\circ}$. Define edge weights $w^{\prime}(u,v)$ by

We solve the LP relaxation (2) for Multiway Cut with weights $w^{\prime}(u,v)$. Let $\{\bar{u}\}$ be the LP solution. Consider the distribution of random cuts ${\cal S}^{\prime}=(S_{1}^{\prime},\dots,S_{k}^{\prime})$ from Lemma 4.4. Let $E^{\prime}$ be the set of edges cut by ${\cal S}^{\prime}$. Similarly to the proof of Theorem 4.5, we define

since the LP value of solution $\{\bar{u}\}$ is at most the value of solution $E^{*}$ (of the multiway instance with weights $w^{\prime}$). Now if ${\cal S}^{\circ}\notin N$ then

We start with an arbitrary feasible multiway cut ${\cal S}^{\circ}$ and iteratively improve it using the algorithm from Lemma 6.10. Once the algorithm returns that the current cut ${\cal S}^{\circ}$ lies in $N$, we output it. Since the cost of the multiway cut decreases by at least $1$ in each iteration, and the initial cost of ${\cal S}^{\circ}$ is polynomial in $n$, the algorithm terminates after polynomially many steps. ∎

Discussion

In this paper, we presented algorithms for stable instances of Max Cut and Minimum Multiway Cut. In conclusion, we briefly discuss what properties of these problems we used. We provide a sufficient condition under which there is an algorithm for stable instances of a graph partitioning problem.

Consider a graph partitioning problem. Our goal is to partition a graph into several pieces, subject to certain constraints, so as to minimize or maximize the weight of cut edges. Consider a metric relaxation for this problem. The relaxation defines a metric $d(\cdot,\cdot)$ on the set of vertices. A combinatorial solution to the problem corresponds to a multicut metric $d(u,v)$: the distance between vertices in one piece is , the distance between vertices in different pieces is $1$. For Max Cut and Multiway Cut, we proved that the metric relaxation is integral when the instance is sufficiently stable; this, in turn, implied the existence of polynomial-time robust algorithms for stable instances of these problems. We summarize the properties that we used in the proof in the following meta-theorem.

Consider a graph partitioning problem and a metric relaxation for it. Suppose that there is a rounding scheme that given a graph $G=(V,E,w)$ and a metric $d(\cdot,\cdot)$ returns a feasible partition such that for some $\alpha\geq 1$ and $\beta\geq 1$:

Then the metric relaxation is integral for $(\alpha\beta)$-stable instances of the problem. Consequently, there is a robust polynomial-time algorithm for $(\alpha\beta)$-stable instances (if the relaxation is polynomial-time solvable). Moreover, there is an algorithm for $(\alpha\beta+\varepsilon)$-weakly stable instances of the problem. (The meta-theorem also holds for a cut maximization/minimization problem with positive and negative weights. Then we require that all four properties $1$, $1^{\prime}$, $2$ and $2^{\prime}$ hold.)

The proof of this meta-theorem repeats the proofs of Theorems 3.1 and 4.5. Note that if a rounding scheme just satisfies property 1 or $1^{\prime}$ then there is an $\alpha$ approximation algorithm for the problem. However, properties $1$ and $1^{\prime}$ alone do not imply that the relaxation is integral. For example, there is a rounding scheme for Max $k$-Cut satisfying $1^{\prime}$, but there is no algorithm for stable instances of Max $k$-Cut (see Claim 5.1). Another example is Minimum Multicut. There is a rounding scheme for the standard LP relaxation of Minimum Multicut with $\alpha=O(\log n)$ . However, this relaxation is not integral even for $(n-2-\varepsilon)$-stable instances of the problem (for every $\varepsilon>0$). Indeed, consider an instance on $(n-1)$ terminals $s_{1},\dots,s_{n-1}$ and one extra vertex $u$; $u$ is connected with $s_{1}$ by an edge of weight $n-2-\varepsilon/2$ and with all other terminals by edges of weight $1$. We need to separate every pair of terminals $s_{i}$ and $s_{j}$. This instance is $(n-2-\varepsilon)$-stable. However, the optimal LP solution is not integral: it assigns $d(u,s_{i})=1/2$ (for every $i$) and $d(s_{i},s_{j})=1$ (for every $i\neq j)$.

References

Appendix A Proof of Lemma 5.6

By rescaling demands we may assume without loss of generality that

Appendix B Remark on Correlation Clustering

In this section, we briefly describe how our results extend to stable instances of the Correlation Clustering problem. The Correlation Clustering problem was introduced by Bansal, Blum, and Chawla and later studied by Charikar and Wirth , and others. Our positive results for stable and weakly stable instances of Max Cut also apply to stable and weakly stable instances of 2-Correlation Clustering. Our negative result when Max $k$-Cut shows that there is no exact polynomial-time algorithm for $\infty$-stable instances of $k$-Correlation Clustering for $k\geq 3$ unless $RP=NP$.

An instance of the $k$-Correlation Clustering problem is a weighted graph $G=(V,E,w)$ in which every edge is labeled with either “$+$” or “$-$”. We denote the set of edges labeled with “$+$” by $E^{+}$ and the set of edges labeled with “$-$” by $E^{-}$. Consider a clustering $\cal C$ of $V$ into $k$ disjoint clusters. For every $u\in V$, let ${\cal C}(u)$ be the cluster that $u$ belongs to. We define the total weight of agreements and disagreements as follows:

The Correlation Clustering problems asks to find a clustering of $V$ into $k$ clusters that maximizes the total weight of agreements, $\mathsf{Agree}_{G}({\cal C})$.

We note that different variants of the problem have been studied in the literature (see Table 1). A good approximate solution for one variant is not necessarily a good approximate solution for the other variants. However, an optimal solution for one variant is also an optimal solution for all other variants. Thus an instance of Correlation Clustering is $\gamma$-stable w.r.t. one objective if and only if it is $\gamma$-stable w.r.t. each of them. Since in this paper we study exact algorithms for $\gamma$-stable instances, all three variants of the problem are equivalent for our purposes. We will assume that our objective is to maximize $\mathsf{Agree}_{G}({\cal C})$.

Our positive results for stable and weakly stable instances of Max Cut also apply to stable and weakly stable instances of $2$-Correlation Clustering. The proofs of Theorem 3.1, Corollary 3.2, and Theorem 6.4 can very easily be modified to deal with the $2$-Correlation Clustering problem. We do not describe the necessary modifications in this paper. Instead, we point out that there is a simple reduction that maps $\gamma$-stable instances of $2$ Correlation Clustering to $\gamma$-stable instances of Max Cut, and weakly stable instances to weakly stable instances. Therefore, every algorithm for solving $\gamma$-stable or $\gamma$-weakly stable instances of Max Cut can be used to solve $\gamma$-stable or $\gamma$-weakly stable instances of 2-Correlation Clustering. We now briefly describe the reduction. Given a graph $G=(V,E^{+}\cup E^{-},w)$, the reduction constructs a graph $G^{\prime}=(V^{\prime},E^{\prime},w^{\prime})$ with

where $W_{\infty}$ is large enough (e.g. $W_{\infty}=2\gamma\sum_{e\in E}w_{e}$). Since the weight of edges $(u,u^{\prime})$ is very large, every maximum cut in $G^{\prime}$ cuts all edges $(u,u^{\prime})$, even if we increase some edge weights by a factor at most $\gamma$. For every 2-clustering $(S,\bar{S})$ of $G$, consider the corresponding cut $(S^{\prime},\bar{S}^{\prime})$ in $G^{\prime}$

Then $\mathsf{Agree}_{G}((S,\bar{S}))=w^{\prime}(E^{\prime}(S^{\prime},\bar{S}^{\prime}))-nW_{\infty}$ (note that the term $nW_{\infty}$ does not depend on $S$). We get that $(S,\bar{S})$ is an optimal 2-clustering if and only if $(S^{\prime},\bar{S}^{\prime})$ is a maximum cut in $G^{\prime}$.

Negative Results.

The Max $k$-Cut problem is a special case of the $k$-Correlation Clustering problem, in which all edges are labeled with “-”. Therefore, the result of Theorem 5.1 applies to the $k$-Correlation Clustering problem when $k\geq 3$.

Appendix C Different Definitions of Weak Stability

In this section, we first prove that Definitions 6.1 and 6.2 are equivalent, and then that Definitions 6.6 and 6.7 are equivalent.

Let $G=(V,E,w)$ be a $(\gamma,N)$-stable instance according to Definition 6.1. Let $(S,\bar{S})$ be the maximum cut in $G$. Consider an arbitrary cut $(T,\bar{T})$ not in $N$. Define a $\gamma$-perturbation $G^{\prime}$ of $G$ by $w^{\prime}(e)=\gamma w(e)$ if $e$ is cut by $(T,\bar{T})$ and $w^{\prime}(e)=w(e)$, otherwise. Since $G$ is $\gamma$-stable, we have $w^{\prime}(E(S,\bar{S}))>w^{\prime}(E(T,\bar{T}))$, and therefore, $w^{\prime}(E(S,\bar{S})\setminus E(T,\bar{T}))>w^{\prime}(E(T,\bar{T})\setminus E(S,\bar{S}))$. We conclude that

Therefore, $G$ is a $(\gamma,N)$-weakly stable instance according to Definition 6.2.

Assume now that $G$ is a $(\gamma,N)$-weakly stable instance according to Definition 6.2. We need to show that for every $\gamma$-perturbation $G^{\prime}=(V,E,w^{\prime})$ and every cut $(T,\bar{T})$, the following inequality holds: $w^{\prime}(E(S,\bar{S}))>w^{\prime}(E(T,\bar{T}))$, or, equivalently, $w(E(S,\bar{S})\setminus E(T,\bar{T}))>w^{\prime}(E(T,\bar{T})\setminus E(S,\bar{S}))$. We have,

Let $G=(V,E,w)$ be a $(\gamma,N)$-stable instance according to Definition 6.1. Let ${\cal S}^{*}$ be the minimum multiway cut. Denote the set of edges cut by ${\cal S}^{*}$ by $E^{*}$. Consider an arbitrary multiway cut ${\cal S}^{\prime}$ not in $N$. Denote the set of edges cut by ${\cal S}^{\prime}$ by $E^{\prime}$.

Define a $\gamma$-perturbation $G^{\prime}$ of $G$ by $w^{\prime}(e)=w(e)$ if $e\in E^{\prime}$ and $w^{\prime}(e)=\gamma w(e)$, otherwise. Since $G$ is $\gamma$-stable, we have $w^{\prime}(E^{*})<w^{\prime}(E^{\prime})$, and therefore, $w^{\prime}(E^{*}\setminus E^{\prime})<w^{\prime}(E^{\prime}\setminus E^{*})$. We conclude that

Therefore, $G$ is a $(\gamma,N)$-weakly stable instance according to Definition 6.7.

Assume now that $G$ is a $(\gamma,N)$-weakly stable instance according to Definition 6.7. We need to show that for every $\gamma$-perturbation $G^{\prime}=(V,E,w^{\prime})$ and every multicut ${\cal S}^{\prime}$, the following inequality holds: $w^{\prime}(E^{*})<w^{\prime}(E^{\prime})$, or, equivalently, $w(E^{*}\setminus E^{\prime})<w^{\prime}(E^{\prime}\setminus E^{*})$. We have,