Maximum cut

The maximum intersection of a graph is a decomposition of its set of nodes into two subsets, so that the total weight of the edges running between the two parts is maximal. In contrast to the minimal cut , the problem is NP-complete .

Formal definition

An undirected graph with a maximal cut

The problem is viewed on an undirected graph . In addition to the graph, there is an edge weight function that assigns a positive real weight to each edge . ${\ displaystyle G = (V, E)}$ ${\ displaystyle w: E \ rightarrow \ mathbb {R} ^ {+}}$

We are looking for a bipartition of the node set , so that the total weight of all edges for which one end node is contained in one and the other end node is contained in the other of the two disjoint subsets and the node set , i.e. either and or and applies. ${\ displaystyle (S, T)}$ ${\ displaystyle V}$ ${\ displaystyle \ sum _ {u \ in S, v \ in T} w (u, v)}$ ${\ displaystyle \ {u, v \} \ in E}$ ${\ displaystyle S}$ ${\ displaystyle T}$ ${\ displaystyle V}$ ${\ displaystyle u \ in S}$ ${\ displaystyle v \ in T}$ ${\ displaystyle u \ in T}$ ${\ displaystyle v \ in S}$

For the special case that all edge weights are the same, i.e. the edge weight function is constant , the problem can also be defined as follows:

We are looking for a subset of , so that the number of edges between and the complementary subset is as large as possible. ${\ displaystyle S}$ ${\ displaystyle V}$ ${\ displaystyle S}$ ${\ displaystyle T = V \ setminus S}$

We are looking for a bipartite subgraph of the graph with a maximum number of edges.

NP completeness

Decision problem

The corresponding decision problem asks for an input and : Is there a section whose value is greater than ? ${\ displaystyle (G, w)}$ ${\ displaystyle b> 0}$ ${\ displaystyle b}$

proof

The problem lies in NP , since a solution ("witness") - however found - can be verified in polynomial time (only the value of the given intersection has to be calculated and checked whether it is).

{\ displaystyle \ geq b}

The problem is also NP-complete, because a reduction of Not-All-Equal-3-SAT is possible: The input consists - as with normal 3-SAT - of a set of clauses with three of the literals . Not-All-Equal-3-SAT now asks: is there an assignment so that every clause contains at least one true and one false literal? A graph is constructed and used as input for the maximum section as follows: ${\ displaystyle C_ {1} \ ldots C_ {m}}$ ${\ displaystyle x_ {1} \ ldots x_ {n}}$

It has knots, labeled with . ${\ displaystyle 2n}$ ${\ displaystyle x_ {1} \ ldots x_ {n}, {\ bar {x_ {1}}} \ ldots {\ bar {x_ {n}}}}$

The non-exclusive assignments of the literals are connected from each clause: Then the edges , and are created; with a clause only and again ; and a clause does not induce any edges. ${\ displaystyle C_ {i} = (a, b, c)}$ ${\ displaystyle (a, b)}$ ${\ displaystyle (b, c)}$ ${\ displaystyle (a, c)}$ ${\ displaystyle C_ {i} = (a, b, b)}$ ${\ displaystyle (a, b)}$ ${\ displaystyle (a, b)}$ ${\ displaystyle C_ {i} = (a, a, a)}$

Draw as many edges between and as often and in total appear in all clauses. ${\ displaystyle x_ {i}}$ ${\ displaystyle {\ bar {x_ {i}}}}$ ${\ displaystyle x_ {i}}$ ${\ displaystyle {\ bar {x_ {i}}}}$

Let be the set of true literals to satisfy Not-All-Equal-3-SAT. Then the section in the graph has the size : It includes all edges that were added in step 3 (since a variable can only be true or false, but not both). It also includes at least edges from step 2, because of the non-mutually exclusive literals in each clause, at least one must be true and the other must be false. ${\ displaystyle X}$ ${\ displaystyle (V, V \ backslash X)}$ ${\ displaystyle 5m}$ ${\ displaystyle 3m}$ ${\ displaystyle 2m}$

If there is no fulfilling assignment for Not-All-Equal-3-SAT, then there is also no section of the size : It is ensured that the section includes all edges inserted in 3 , but it cannot include the edges required from 2 , as it There were not enough non-contradicting literals in the individual clauses in the Boolean formula. Alternatively: If the graph has a section of the same size , this must first contain all edges from 3 (due to the summation of and otherwise there would be no maximum). If it now contains further edges, then enough consistent clauses for a suitable assignment must have existed in the Boolean formula. ${\ displaystyle 5m}$ ${\ displaystyle 3m}$ ${\ displaystyle 2m}$ ${\ displaystyle 5m}$ ${\ displaystyle x}$ ${\ displaystyle {\ bar {x}}}$ ${\ displaystyle 2m}$

Approximation algorithms

2 approximation

The partitioning of the graph is determined by the status of the node (on / off). An attempt is now made to maximize the total value of the "good" edges; by definition, these are all edges between the partitions. A "flip" operation shifts a node from one partition to the other (switches it on or off). A local maximum is achieved by stringing together flips by performing random flips as long as this improves the overall score (since the overall score is limited and it increases with each operation, this process actually terminates at some point). The problem, however, is that the running time is only pseudopolynomial as a function of the total weight.

(2+ ε ) approximation

In order to actually achieve a polynomial running time, only flips are carried out that bring a great improvement in weight, more precisely: increase the weight ratio by at least the factor . As a result, the weight is multiplied with a linear number of flips, whereby the maximum weight can be achieved in logarithmic steps; however, the solution becomes somewhat less precise, since even if a small improvement were still possible, this will no longer be made. ${\ displaystyle / | V |}$ ${\ displaystyle (1+ \ epsilon)}$

literature

For NP completeness: Guan-Shieng Huang: Theory of Computation . (PDF; 404 kB). P. 7 ff.
Regarding the approximation algorithms: Jon Kleinberg , Eva Tardos : Algorithm Design. Pearson International Edition. Pearson et al., Boston MA et al. 2006, ISBN 0-321-37291-3 , p. 676 ff.