У статті розглянуто властивості верхніх оцінок для квадратичної задачі про максимальний
k-плекс у неорієнтованому графі. Проаналізовано зв’язок квадратичної задачі для 1-плекса з відомим формулюванням квадратичної задачі для знаходження максимальної кліки графа. Наведено
лагранжеві двоїсті оцінки для найпростіших квадратичних задач та показано, що їх можна покращити при додаванні функціонально надлишкових обмежень.
The paper considers properties of upper bounds in the quadratic problem about maximum k-plex in
undirected graph. The notion of k-plex is introduced to make the notion of clique to be less restrictive. These
notions are widely used in sociology to identify specific subgroups of the population. They also can be used
to clusterize data, to optimize information flows in networks, to find targeted subgroups for advertising and
promotion, etc.
In a general case, optimization problems of finding maximum cliques and k-plexes are NP-hard. For this
reason, in the maximum clique problem, finding dual bounds is a widely used approach. These bounds may
be used directly, especially if the exact bound can be found, or they may be an integral part of other
algorithms similar, for example, to the branch-and-bound algorithm.
The relationship between the quadratic problem for 1-plex and a known formulation of the quadratic
problem for finding the maximum clique in a graph is analyzed. Lagrangian dual quadratic bounds for the
simplest quadratic problems are reported; it is shown that these bounds can be improved by adding
functionally superfluous constraints. This approach was proposed by N. Z. Shor for the maximum clique
problem and also used in polynomial optimization.
Different ways to generate functionally superfluous constraints are proposed. On the example of
maximum 2-plex problem different formulation of the resulting quadratic programming problem are
discussed and compared. This does not mean, however, that the considered superfluous constraints give an
exact dual bound in any quadratic problem. To improve Lagrangian dual quadratic bounds, other ways of
generation of superfluous constraints can also be used.
