Stable maximum

The reader is returned to the article graph theory for an introduction to the graphs and the article Lexique of the graph theory for the elementary definitions.

The problem of the stable maximum is perfectly equivalent to that of the clicks maximum and very near to the transverse minimum.

Definition of the problem

The problem of the stable maximum arises in a graph which one can consider simple since its possible orientation or multiple edges does not play any part here (one can get rid of the tops incident to the loops because they do not belong to any stable of the graph).

Either G a simple graph, and or S a stable subset of the unit X of the tops of G .

S is maximum (by-report/ratio with inclusion) if it is contained in no other stable whole of G .
S is of cardinality maximum if its cardinality is equal to or higher than the cardinality of any other stable of G .

A maximum cardinality implies maximum, but not the reverse. The number of stability of G , noted $\ alpha (G)$ , is the cardinality of a stable maximum. The problem of the stable maximum consists in determining $\ alpha (G)$ being given a graph G . This problem is Np-complete within the meaning of the Théorie of complexity.

Now let us provide G with a weighting by associating with each top X of X a reality p (X) called the weight of X . The weight P (Y) of a subset Y of X is then equal to the sum of the weights of the tops of Y .

S is maximum weight if the weight of S is higher or equal to the weight of any other stable of G .

The problem of the stable maximum in a balanced graph consists in determining the maximum weight of stable of G . Let us note, that unless the function p is not positive, a stable maximum is not necessarily maximum in the balanced graphs.

Close problems

Since the problem of the stable maximum is Np-hard, all the problems of this class can be expressed like a problem of stable maximum (and vice versa). However, certain problems, as those which we present below, are more directly connected to him.

Problème of the clicks maximum : It is a question of determining the maximum weight of a clicks of G . Equivalence is total, even on the level of the algorithms of Approximation, it is enough to reformulate the problem in the graph complementary to G .

Problem of the minimum transerval (or of the cover minimum by tops): It is a question of determining a transverse minimum. Equivalence comes owing to the fact that the complementary one to transverse of G (compared to the unit X ) is stable of G . Attention this problem is not equivalent within the meaning of the Approximation.

The following problems require only one simple transformation to be reformulated like a problem of stable maximum:

Problem of the maximization of a function pseudo Boolean (for example the function $F (x_1, x_2, x_3) = 3 x_1 \ overline {x_2} + 4 x_1 \ overline {x_2} x_3 + 6 x_1 \ overline {x_3} + 7 x_2 \ overline {x_3}$ ). Equivalence passes by the construction of an auxiliary graph. Let us associate with each students' rag procession of the function a top of the graph, to which one gives a weight equal to the coefficient of the students' rag procession. Let us connect two tops by an edge when the Boolean product of the two corresponding students' rag processions is null. Thus the maximum of the function is equal to the maximum weight of stable of the graph. With the function F given in example, one obtains the following graph:

Ici the stable maximum is composed of tops 3 and 4 and has as a weight 13, the maximum of F is worth 13 (it is reached by

x_1=1, x_2=1, x_3=0

, i.e. when only the third and fourth students' rag processions are worth 1.

Reference

B Ambert and P Castéra, Realization of an effective algorithm for the determination in stable whole of maximum weight of a graph , Memory of engineer of the Institute of Data processing of Company (IIE-CNAM), Paris 1981

Random links: