Symmetric Linear Programming Formulations for Minimum Cut with Applications to TSP

The minimum cut problem is one of the most fundamental problems in computer science and has numerous applications in other fields. Consequently, there has been a vast amount of research on the topic (see [8] for an overview). In this problem you are given an undirected graph $G$ on $n$ nodes and an undirected non-negative cost function $c$ on every pair of nodes denoting the capacity of the edges in the graph. In the global cut problem the goal is to find a non-empty set $S\subset V=\{1,2,\dots,n\}$ where $S\neq V$ such that the sum of the edge weights crossing the cut $(S,V\setminus S)$ is minimized. In the $s,t$ cut problem it must be the case that $s\in S$ and $t\in V\setminus S$ where $s,t\in V$ are given. In the fixed sized partition minimum cut problem, the set $S$ must have size $\alpha$ where $\alpha$ is an input parameter. The $s,t$ cut and global minimum cut problems are polynomially time solvable, but the fixed size partition minimum cut problem is known to be NP-Hard.

It is well known that the minimum cut problem yields polynomial time algorithms and a variety of efficient algorithms are known [8, 12] as well as efficient parallel algorithms [13, 14]. One widely used technique is mathematical programming. A few integer linear programs are known for the minimum cut problems [8, 6] and for several of them the LP relaxation gives exact solutions to the minimum cut problem (global or $s,t$). Like most problems, finding a linear programming relaxation for a given problem that is different than the obvious relaxation is generally a challenging task. The smallest known linear programming relaxation of the global mincut problem, called the $w$-LP, was given in [6]. This formulation has $O(n^{2})$ variables and $O(n^{3})$ constraints. From a theoretical viewpoint, it is interesting to determine the bounds of the smallest linear program for a given problem, since small linear programs can lead to more efficient algorithms in practice. For the minimum cut problem, finding a small relaxation not only can improve the performance for finding the minimum cut of a graph, but can be also instrumental to the solution of other fundamental problems.

It was shown by in [18] that no symmetric LP can have polynomial size for TSP or perfect matching. Roughly speaking, an LP is said to be symmetric if the nodes in a graph can be permuted without changing the feasible region. Further, it is known that certain classes of LP’s can be lifted to give symmetry [18]. This was originally thought to be a way to show that not every problem in P has a polynomial size LP. In particular, Yannakakis proved also that there are no compact LP formulations to perfect matching that have symmetricity, and he argued that the lack of existence of a compact LP formulation to perfect matching that has symmetricity is strong evidence there is no compact LP formulation to perfect matching (even asymmetric). Indeed, the underlying perfect matching problem has symmetricity. Thus, if there were such an asymmetric LP formulation then intuitively one could likely lift it to a slightly larger LP formulation that does have symmetricity. But this contradicts Yannakakis’ result. It turns out that Yannakakis was correct, and recently, [17] showed that the matching polytope does not have a polynomial size linear program.

In the Traveling Salesperson Problem (TSP), a salesperson wants to visit a set of cities and return home [11, 10]. There is a cost $c_{ij}$ of traveling from city $i$ to city $j$, which is the same in either direction for the Symmetric TSP. The objective is to visit each city exactly once, minimizing total travel costs. The subtour elimination linear program is a natural and easily solvable linear programming relaxation of TSP:

There is no natural compact LP relaxation for TSP which is stronger than the subtour elmination linear program relaxation. The TSP uses the minimum cut as a subroutine [6].

Despite most work focusing on finding small non-exact linear programming formulations, there is another property that non-exact linear programming formulations can have for problems in P which is of interest to study. Consider the minimum cut problem. Say that one finds a linear programming formulation which returns a non-exact solution, yet one can prove that the LP’s solution is exact when the cost function (input graph) is a Hamiltonian cycle. Although the LP is non-exact for general graphs, we actually can use the LP to improve the subtour relaxation for the TSP problem. Indeed, we show in this paper, if the LP relaxation were not an exact formulation of the minimum cut problem (but exact on Hamiltonian cycles), it can be used to strengthen the subtour LP relaxation for the TSP problem.

We call this feature of the LP interesting. Interesting LPs are not limited to the relationship between minimum cut and TSP. For example, suppose we had a compact relaxation of the minimum directed cut problem, but not necessarily an exact formulation. Further assume that this relaxation gives the exact answer of 1 when the cost function is an arborescence. Then, either this is an exact formulation of directed cut or we can strengthen the LP relaxation for the directed arborescence problem.

This leads to a somewhat unintuitive situation. One would want to find an LP formulation that is exact for computing a minimum cut when the graph is a Hamiltonian cycle, but simultaneously as loose as possible for computing the minimum cut for any other graph. In this case, one can strengthen the subtour LP relaxation for the TSP problem by the largest amount. Indeed, any time the minimum cut LP gives a non-exact solution this is a certificate that the objective function is outside the TSP polytope, even if this solution were in the subtour TSP relaxation. We can then cut off this point in a new TSP relaxation, thus making it better than the subtour relaxation.

• 1.

  The $\alpha$-LP gives the optimal solution for the fixed size partition minimum cut problem when the input graph is an unweighted Hamiltonian cycle for any $\alpha\leq n/2$ (has the Hamiltonian cycle property).

• 2.

  The $\beta$-LP is a relaxation of the $\alpha$-LP which also has the Hamiltonian cycle property.

• 3.

  The $\gamma$-LP is a further relaxation of the $\alpha$-LP which is within $\frac{8}{9}$ of the $\alpha$-LP, but creates a smaller set of LPs which need to be solved to approximate the minimum cut.

Now, we do not know for general graphs if the $\alpha$-LP returns at least that of the minimum global cut. However, if this is the case, then by extending the $\alpha$-LP to include all possible values of $\alpha$ this will be the smallest known LP for the global minimum cut problem that is symmetric. The extension of the $\alpha$-LP to include all values of $\alpha$ has $O(n^{3})$ variables and $O(mn^{2})$ constraints where $m$ is the size of the support of the cost function. This compares to the previous best known formulation with $O(mn^{2})$ variables and $O(mn^{2})$ constraints which can be obtained by extending the standard formulation of $s,t$ minimum cut. Beyond being interesting from a theoretical viewpoint, symmetric LPs are also typically easier to analyze than other LPs.

Alternatively, say that the $\alpha$-LP admits feasible solutions of value smaller than the minimum global cut. In this case, we can use the $\alpha$-LP to obtain new valid inequalities for the TSP. Here, by leveraging the fact that the $\alpha$-LP is optimal for Hamiltonian cycle graphs, we can show that this LP can be exploited to strengthen the standard subtour relaxation for TSP. We show this by using compact optimization methods. Thus, we have a favorable situation, i.e., this new formulation either gives one of two interesting conclusions.

We then relax the $\alpha$-LP further and create a new model we call the $\beta$-LP. While the $\alpha$-LP assumes $\alpha$ is an integer, in the $\beta$-LP we relax this assumption by allowing $\alpha$ to be the convex combination of two consecutive integers. We show that the $\beta$-LP has the same Hamiltonian cycle property as the $\alpha$-LP even though the $\beta$-LP is a relaxation. We then show that in some special cases that the $\alpha$-LP and $\beta$-LP are lower bounded by the minimum cut.

Lastly, we extend the $\beta$-LP relaxation and give another relaxation which is $1/(1+\epsilon)$-approximation for the minimum cut problem on Hamiltonian cycle graphs and a $\frac{8}{9}$-approximation for the minimum cut problem when $\epsilon=1$. This new relaxation has $O(n^{2}\log_{1+\epsilon}n)$ variables and $O(mn\log_{1+\epsilon}n)$ constraints for any $\epsilon>0$. We obtain this by extending the $\beta$-LP to express $\alpha$ as the convex combination of two integers, $\gamma$ and $\lceil(1+\epsilon)\gamma\rceil$. The $\beta$-LP has size $O(n^{2})$ variables by $O(mn)$ constraints. By allowing variable sizes in the partitions where $\alpha$ is in the range $\gamma\leq\alpha\leq 2\gamma$, we can geometrically choose a logarithmic number of values for $\gamma$. For these values, we bound the objective of the $\gamma$-LP by $16/9$ on Hamiltonian cycle graphs. Although this LP is not exact for the minimum cut problem on Hamiltonian cycle graphs, one can still use this relaxation to potentially improve the solution for the TSP relaxation, while yielding a significantly smaller LP.

We are going to construct symmetric LPs that solve or approximate fixed sized partition and (global) minimum cut. A cut in an undirected graph $G=(V,E(V))$ partitions the vertex set $V$ of $n$ vertices into a set of top nodes and a set of bottom nodes, with the edges in the cut going between these two sets. Given a vector $c_{ij}\geq 0$ of capacities and edge variables $x_{ij}$ indicating whether edge $\{i,j\}$ is in a cut for $\{i,j\}\in E(V)$ we want to minimize $c\cdot x$. Minimum $s$-$t$ cut where $s$ is specified to be on the bottom and $t$ is specified to be on the top is the most usual type of minimum cut problem (without such a specified pair of nodes it is the minimum global cut problem).

For the definition of a symmetric linear program, we use the definition given in [18]. Let $\pi$ denote a permutation of the nodes. In the complete graph, a permutation of the nodes defines a mapping of the costs of the edges of the graph such that each cost $c_{ij}$ is mapped into $c_{\pi(i)\pi(j)}$. Let $P(x,y)$ denote a polytope over the variables $x_{ij}$ on the edges of a graph and other variables $y$. A polytope $P$ of a linear program is said to be symmetric if for all permutations $\pi$ of the nodes the new variables $y$ can be extended so $P$ remains invariant. A linear program can be seen to yield a symmetric polytope if renaming the variables for the nodes yields the same linear program. Note that, however, a linear program need not necessarily have this property to be symmetric.

Minimum $s$-$t$ cut has an easy (naturally integer) LP formulation, shown below. Let node variables $h_{i}$ indicate whether $i$ is on top ($h_{i}=1$) or on bottom ($h_{i}=0$) in a cut. Furthermore, let $x_{ij}$ be edge variables indicating which edges are in the cut.

One can also formulate the NP-hard maximum cut problem. A naive IP formulation and LP relaxation is

However, setting $h=1/2$ shows that this is a weak LP relaxation.

Suppose one constrained minimum cut so that it has a fixed sized partition with exactly $\alpha\leq n/2$ nodes on top. Note that one can always assume $\alpha\leq n/2$ since one side of the cut always at most $n/2$ nodes. Call this the minimum $\alpha$-cut problem, which is also an NP-hard problem [9]. We note that when $\alpha=n/2$ this is equivalent to the minimum edge bisection problem. We will now construct an LP relaxation for this problem. Let $\delta(i)$ be the edges adjacent to $i$ in $E$ and $x(\delta(i))=\sum_{ij\in\delta(i)}x_{i,j}$. For $i\in V$ consider $x(\delta(i))$. Suppose $h_{i}=0$. Then there are $\alpha$ nodes opposite $i$, so $x(\delta(i))=\alpha$. Now, suppose $h_{i}=1$. Then there are $n-\alpha$ nodes opposite $i$, so $x(\delta(i))=n-\alpha$. Hence, it is always the case that

Also, for distinct $i,j,k\in V$ we have the (metric) triangle inequality property that $x_{i,j}\leq x_{i,k}+x_{k,j}$.

Here is the first LP relaxation:

The above relaxation is stronger than we need for the results in this paper, we will refer to it as the old $\alpha$-LP. It can be relaxed to the following, which we call the (new) $\alpha$-LP:

We only need the triangle inequalities $x_{i,j}\leq x_{i,k}+x_{k,j}$ when $c_{j,k}>0$ in our proof of Theorem 3.10. The remaining triangle inequalities are unused. We obtain constraint (4) by summing the constraints giving $x(\delta(i))$ in the previous LP. We emphasize that this $\alpha$-LP has size $O(mn)\times O(n^{2})$ as we only need a subset of the triangle inqualities.

Denote the $\alpha$-LP relaxation’s feasible region by

where $z^{\alpha}=[x^{\alpha},h^{\alpha}]$. The $\alpha$-LP constraint (4) is the only constraint which typically appears in min-cut relaxations while constraints (3), (5), and (6) generally appear in max-cut linear programming relaxations.

In the next section we will bound the objective value of this LP. Before we do that, we introduce the $w$-LP of [6] which the LP can be compared to. In this linear program $w_{k}=1$ when $k$ is the last node (numerically) on top in the cut (where, w.l.o.g., we can assume that node $n$ is always on bottom).

While the $w$-LP is asymmetric, the $\alpha$-LP is symmetric.

Denote the convex hull of the set of the incidence vectors of all the cuts of a complete graph $G=(V,E)$ by $Q$. An LP whose feasible region $P\supset Q$ that minimizes or maximizes an objective function given by edge coefficients $c$ is a relaxation of the cut problem. If the LP is meant to bound the minimum cut of $G$ it is said to be a relaxation of the minimum cut problem. We introduce the dominant polyhedron of a polytope. The polyhedron $dom(Q)$ is a set of points $y$ such that there exists an $x\in Q$ such that $y\geq x$. An LP relaxation of the minimum cut problem is an LP mincut formulation if its feasible region $P\subset dom(Q)$.

We now introduce a surprising principle for creating LP relaxations of the TSP. Consider any linear program

on the edge variables $x$ of a complete graph (and possibly other variables). If for any Hamilton cycle, when its incidence vector is plugged into $c$ the minimum of this LP is a constant $\eta>0$, then this LP is said to satisfy the Hamilton cycle property. If this LP is symmetric on the $x$ edge variables and the nodes, its minimum $\eta$ will automatically be a constant for all Hamilton cycles. If this constant is strictly positive, the LP will then satisfy the Hamilton cycle property. An LP that satisfies the Hamilton cycle property gives rise to an LP relaxation of the TSP through duality methods. Let $\hat{c}$ be the costs for the TSP. Let $c$ be the variables of the TSP relaxation, which are so named to relate to the cost function of the LP satisfying the Hamilton cycle property. The TSP relaxation is given by

With respect to the subtour elimination relaxation of the LP, the idea of LP (9) is to keep the degree constraints, but replace the subtour elimination constraints with the dual of LP (8). Indeed, if the objective function $c^{*}$ plugged into LP (8) satisfying the Hamilton cycle property has a minimizer $x^{*}$ with objective value strictly less than $\eta$, this LP solution is a certificate that $c^{*}$ is not in the TSP polytope, and we say $c^{*}$ is certified by LP (8) not to be in the TSP polytope. Moreover, $(y,c^{*})$ is not feasible for any $y\geq 0$ in the above LP relaxation of the TSP. Also, $c^{*}$ violates the valid TSP inequality $x^{*}\cdot c\geq\eta$.

Suppose that the LP satisfying the Hamilton cycle property has the triangle inequalities as constraints either explicitly or implicitly. That is,

for all distinct triples $i,j,k$ of nodes (where the order of the 2 endpoint nodes for an edge is arbitrary in the undirected graph).

Proof: Suppose the minimizer for this LP (8) is $x^{*}$ and that the minimum cut of $c^{\prime}$ is at least $2$. Normalize $c^{\prime}$ so that the minimum cut of $c^{\prime}$ is exactly 2. By assumption, $c^{\prime}\cdot x^{*}<\eta$.

Define splitting off by $\epsilon$ at a node $k$ with nodes $i$ and $j$ to be the operation of taking nodes $i,j,k$ and decreasing $c_{i,k}$ and $c_{j,k}$ by $\epsilon$ while increasing $c_{i,j}$ by $\epsilon$ for some fixed $\epsilon$. In Lovász splitting off, this is done only on nodes $i,j,k$ such that the minimum global cut stays the same after the operation. It is known [15] that if the cut $(\{k\},V\setminus\{k\})$ is not a minimum cut, then there exist nodes $i$ and $j$ and $\epsilon>0$, such that we can perform Lovász splitting off by $\epsilon$ at $k$ with nodes $i$ and $j$. Thus, we iteratively perform Lovász splitting off at nodes $k$ such that $(\{k\},V\setminus\{k\})$ is not a minimum cut, until every node has fractional degree 2. During this process, we obtain intermediate vectors $c^{\prime\prime}$ and eventually reach a final vector $c^{*}$ that has fractional degree $2$ at every node.

Since Lovász splitting off keeps the minimum global cut the same, then $c^{*}$ is a feasible subtour point. Due to the triangle inequalities in (8), at each step $c^{\prime\prime}\cdot x^{*}<\eta$ because $c^{\prime}\cdot x^{*}<\eta$ and the objective decreases at each step, specifically, $c^{\prime\prime}\cdot x^{*}=c^{\prime}\cdot x^{*}+\epsilon(x^{*}_{i,j}-(x^{*}_{i,k}+x^{*}_{k,j}))$. In the end $c^{*}\cdot x^{*}<\eta$, and without loss of generality one can choose $c^{*}$ to be a subtour extreme point.

Now suppose the LP (8) is a relaxation of minimum global cut.

Proof: Suppose $c^{*}$ is feasible for (9) but that $c^{*}$ is not in the subtour polytope, i.e., the minimum global cut of $c^{*}$ is less than $2$. Plug $c^{*}$ into (8). Since LP (8) is a relaxation of minimum global cut, its minimizer $x^{*}$ satisfies $c^{*}\cdot x^{*}\leq mincut(c^{*})<2$. Thus, $y\cdot b\geq 2$ in (9) is violated since $y\cdot b\leq c^{*}\cdot x^{*}$, by duality, and $c^{*}$ is not feasible for (9) after all.

Now suppose the LP satisfying the Hamilton cycle property is a relaxation of minimum cut and also includes the triangle inequalities. Then either this LP is an exact minimum cut formulation or it leads to a TSP relaxation that is strictly stronger than the subtour relaxation of the TSP.

Proof: Lemma 3.2 implies that the feasible region for LP (9) is a subset of the subtour polytope. In the case where (8) is not an exact minimum cut formulation, we show that it is a strict subset.

Suppose (8) is not an exact minimum cut formulation. Then there exists an objective $c^{\prime}$ such that $mincut(c^{\prime})=2$ but $c^{\prime}\cdot x^{*}<2$ for a minimizer $x^{*}$ of (8). By the reasoning of Lemma 3.1 there exists a $c^{*}$ in the subtour polytope such that $c^{*}\cdot x^{*}<2$. By the reasoning of Lemma 3.2, $c^{*}$ is then not in the relaxation (9).

We provide three examples of LPs satisfying the Hamilton cycle property here and more examples in the next section.

Consider the following linear program where $s,t\in V$:

If the integrality constraint $h\in\{0,1\}$ is added to (10), the resulting integer program is an IP formulation of minimum $s,t$ cut. Hence (10) is an LP relaxation of minimum $s,t$ cut. It is readily shown here to satisfy the Hamilton cycle property.

Proof: Let $H$ be an arbitrary Hamilton cycle and $c$ be its incidence vector. The cycle $H$ can be decomposed into two vertex disjoint (except at ends) $s,t$ paths $P^{1}$ and $P^{2}$. Consider $P^{1}$ first. Let the $k+1$ vertices in order in the path $P^{1}$ starting at $s=v_{0}$ be $v_{0},v_{1},\ldots,v_{k}=t$. For $i\in\{0,\ldots,k-1\}$ we have

Summing these up over the edges of the path $P^{1}$ yields a telescoping sum

Therefore we have

It is easy to show the bound of $2$ is attained.

If $(x^{*},h^{*})$ is a minimizer of (10) then without loss of generality in what follows, we may set

For what follows next, we introduce the concept of a disjunctive mathematical program [2].

Consider the feasible regions $Q_{t}$ that arise from (10) when binary integrality constraints are placed on $h$ and one sets $s:=n$ and varies $t$ to be in the set $\{1,\ldots,n-1\}$. This is an IP formulation of minimum $s,t$ cut. Consider the disjunctive program of these $n-1$ minimum $s,t$ cut integer programs. The feasible region of this disjunctive program is the convex hull of $\bigcup_{t}Q_{t}$. This disjunctive program can be seen to be an IP formulation of the minimum global cut problem. Now remove the binary integrality constraints on the $h$ variables. The resulting feasible regions are $P_{t}$. The feasible region $P_{t}$ is a relaxation of minimum $s,t$ cut for each $t$. The disjunctive program of these $n-1$ LP relaxations has a feasible region which is the convex hull of $\bigcup_{t}P_{t}$. Hence, it is a relaxation of minimum global cut.

Proof: The disjunctive program above is a relaxation of minimum global cut. Its feasible region is the convex hull of $\bigcup_{t}P_{t}$. It satisfies the Hamilton cycle property with $\eta=2$ by Theorem 3.4. It also includes the triangle inequalities as constraints when at optimality by Lemma 3.5. Hence the result follows from Theorem 3.3.

This theorem intuitively says that since (10) satisfies the Hamilton cycle property, it is likely that (10) is an exact LP formulation of minimum $s,t$ cut. Indeed, this turns out to be the case.

Next consider the following linear program.

Proof: Let $c$ be the incidence vector of an arbitrary Hamilton cycle. Let $c^{0}:=c$. For each node $k$, construct a Hamilton cycle vector $c^{k}$ on the set of nodes $\{k+1,\ldots,n\}$ from a Hamilton cycle vector $c^{k-1}$ as follows. Let $i_{k}$ and $j_{k}$ be neighbors of $k$ in the Hamilton cycle of $c^{k-1}$. Remove these two edges incident to $k$ and replace them with the edge $i_{k}j_{k}$. The result of this is the Hamilton cycle vector $c^{k}$. We now derive a chain of inequalities for feasible solutions of (11).

Thus the Hamilton cycle property is satisfied.

The LP (11) is a subset of the LP (7). Hence (11) is an LP relaxation of minimum cut. However, Theorem 3.3 does not apply here unless the triangle inequalities are added to (11). So whether (11) leads to a stronger relaxation of the TSP than the subtour relaxation has not been resolved yet.

For proving the Hamilton cycle property of the $\alpha$-LP, we need the following lemma:

There is a symmetric optimal solution of the $\alpha$-LP when $c$ is the incidence vector of a Hamiltonian cycle.

Now we show that the $\alpha$-LP (1) satisfies the Hamilton cycle property.

Proof sketch: Because of the permutation symmetry of (1), we may make a remarkable assumption. That is, we may assume that the Hamilton cycle is simply going from $1$ to $n$ in order and back to $1$ again. But there is even another amazing consequence of this symmetry. We may also take a symmetric optimal solution where $x_{e}=K$ for all $e$ in the canonical Hamilton cycle and $h_{i}=\alpha/n$ for all nodes $i$. Since $x$ is an optimal solution, and 2 is an upper bound for the minimum objective value of the old $\alpha$-LP, we know that $K\leq 2/n$. We will show that $K$ must equal $\frac{2}{n}$, by exploiting the fact that $x$ is a feasible solution to the old $\alpha$-LP, thus, yielding the theorem.

By Lemma 3.8 and Lemma 3.9, $x_{n,j}\leq x(P_{n,j})=jK$ where $P_{n,j}$ is the shorter path from $n$ to $j$ in the Hamiltonian cycle for each $j\in\{1,\ldots,\alpha-1\}$. Similarly, $x_{n,n-j}\leq jK$ for each $j\in\{1,\ldots,\alpha-1\}$. Finally, by the maxcut constraints, we have $x_{n,j}\leq h_{j}+h_{n}=\frac{2\alpha}{n}$ for each $j\in\{\alpha,\ldots,n-\alpha\}$.

Combining these, we get

Now,

Hence we obtain

Since $K\leq 2/n$, we obtain

However, the degree constraint from the old $\alpha$-LP (1) says that $x(\delta(n))=(n-2\alpha)h_{n}+\alpha,$ thus, it must be the case that $K=2/n$, and the theorem follows.

We only used the triangle inequalities $x_{i,j}\leq x_{i,k}+x_{k,j}$ when $c_{j,k}>0$ in the proof of Theorem 3.10. Thus, the old $\alpha$-LP has size $O(mn)\times O(n^{2})$ as we only need a subset of the triangle inqualities.

In this section we show that when the input graph is a single cycle on all of the nodes of the graph and all edges of the graph have unit (1) capacity then the new $\alpha$-LP gives an exact solution. That is, we show the following theorem.

To show this for the $\alpha$-LP, we will in fact show that the Hamiltonian cycle property holds for a relaxation, called the $\beta$-LP. We relax the $\alpha$-LP by expressing $\alpha$ as the convex combination of two integers. This gives the $\beta$-LP which has the following form:

We will use $\beta_{2}=\beta_{1}+1$ and $\alpha=\lambda\beta_{1}+(1-\lambda)\beta_{2}$ for this section.