Planar max-cut

From Cophy
Jump to: navigation, search



A cut in a weighted undirected graph G = (V,E) is defined by vertex set SV as the set of all edges with exactly one endpoint in S. The weight of a cut is the sum of the weights of its edges. Now, the max-cut problem is to find a cut of G with maximum weight. There has been a lot of interest in max-cut problems. These problems have many applications, cf. ground state calculations of Ising spin glasses, but are hard to solve in general.

But, there exist a few special cases that can be solved efficiently. One is the case if the underlying graph is planar.

It was shown independently by [Hadlock (1975)] and by [Dorfman and Orlova (1972)] that max-cut on planar graphs is equivalent to finding eulerian subgraphs in its dual graph.

Later on [Bieche et al. (1980)], [Barahona (1982,1983,1993)] [Barahona et al. (1982)],

refined these ideas further and showed that max-cut on graphs not contractible to K5 can be solved in polynomial time today.

The method

In [Barahona (1993)] it is exploited that a graph not contractible to K5 can be decomposed

into planar graphs and graphs with eight vertices V8
The graph V_8
and this

can be used to find a max-cut in graphs not contractible to K5. The max-cut on the graph V8 is solved by enumeration and on the planar graph the problem is solved by following a general scheme that is common to many solution approaches. We state here this scheme:

General scheme

Algorithm: Max-cut on planar graphs

  1. build dual graph Gd of the planar input graph G
  2. transform Gd in an appropriate way to build an auxilliary graph Gt
  3. calculate an optimum weight perfect matching M in Gt
  4. M induces an eulerian subgraph Gd [Euler] in Gd
  5. Gd [Euler] corresponds to a max-cut in G

Roughly speaking the algorithms follow the same algorithmic scheme, that we stated in the above pseudocode.

Being more concrete, at first the dual graph is constructed which is then transformed to an auxilliary graph such that an optimum weighted perfect matching in this auxilliary graph yields subgraphs in the dual, such that each vertex has even degree. In fact those subgraphs are Eulerian and by the known one-to-one correspondence between max-cut in the primal graph and eulerian subgraphs in its dual graph the problem can be solved by the matching computation.

As this general scheme is common to many approaches solving max-cut on planar graphs and fast implementation exists that solves the problem for graphs with million of nodes, which use fast matching procedures that build on the planar seperator theorem stated by [Lipton, Tarjan (1979)], cf. [Pardella, Liers (2008)] and [Liers, Pardella (2008)].


Consider as an example the planar drawing of a graph G = (V,E) in the following figure.

Example planar primal graph.jpg

G consists of seven vertices V = {1,2,...7} and eight faces VD = {A,B,...H}. Vertices are labeled with numbers and faces with capital letters. Edge weights are given as edge subscripts.

Example planar dual graph.jpg

A matching on a (not shown) appropriated auxilliary graph would then e.g. yield the shown optimum-weight Eulerian subgraph of the dual as the blue edges form a simple cycle forming the edge set of the induced subgraph, and thus a max-cut of the primal graph.

Example planar cut.jpg

The cut edges are coloured red and the corresponding Eulerian subgraph in the dual is depicted in blue. The green vertices belong to the same partition.

Personal tools