Under study is the complexity status of the independent set problem in a class of connected graphs that are defined by functional constraints on the number of edges depending on the number of vertices. For every natural number C, this problem is shown to be polynomially solvable in the class of graphs, On the other hand, this problem is proved to be not polynomially solvable in the class of graphs, for every unbounded nondecreasing function f(n): ℕ → ℕ, such that exponent of this function grows faster than a polynomial function of n. The latter result is true if there does not exist a subexponential algorithm for solving the independent set problem.

The notion of a boundary class of graphs is a helpful tool for the computational complexity analysis of graph theory problems in the family of hereditary classes. Some general and specific features for families of boundary classes of graphs for the vertex *k*-colorability problem and its “limit” variant, the chromatic index problem, were studied by the author earlier. In the present article, these problems are considered in application to the edge version of the colorability problem. It turns out that each boundary class for the edge 3-colorability problem is a boundary class for the chromatic index problem; however, for each *k > *3, there exist uncountably many boundary classes for the edge *k*-colorability problem each of which is not a boundary class for the chromatic index problem.We formulate some necessary condition for the existence of boundary classes of graphs for the vertex 3-colorability problem which are not boundary for the chromatic index problem. To the author’s mind, this condition is never satis.ed and so there are no such boundary classes for the vertex 3-colorability problem.

We prove the polynomial solvability of the independent set problem for some family of classes of the planar subcubic graphs.

The notions of boundary and minimal hard classes of graphs, united by the term “critical classes”, are useful tools for analysis of computational complexity of graph problems in the family of hereditary graph classes. In this family, boundary classes are known for several graph problems. In the paper, we consider critical graph classes in the families of strongly hereditary and minor closed graph classes. Prior to our study, there was the only one example of a graph problem for which boundary classes were completely described in the family of strongly hereditary classes. Moreover, no boundary classes were known for any graph problem in the family of minor closed classes. In this article, we present several complete descriptions of boundary classes for these two families and some classical graph problems. For the problem of 2-additive approximation of graph bandwidth, we find a boundary class in the family of minor closed classes. Critical classes are not known for this problem in the other two families of graph classes.

The notion is introduced of an expanding operator for the independent set problem. This notion is a useful tool for the constructive formation of new cases with the efficient solvability of the problem in the family of hereditary classes of graphs and is applied to hereditary parts of the set Free({P_5,C_5}). It is proved that if for a connected graph G the problem is polynomial-time solvable in the class Free({P_5,C_5,G}) then it remains so in the class Free({P_5,C_5,G*O_2,G+K_1,p}) for every p. We also find two new hereditary subsets of Free({P_5,C_5}) with polynomially solvable the independent set problem that are not a corollary of appling the revealed operators.

MDS matrices are widely used as a diffusion primitive in the construction of block type encryption algorithms and hash functions (such as AES and GOST 34.12–2015). The matrices with the maximum number of 1s and minimum number of different elements are important for more efficient realizations of the matrix-vector multiplication. The article presents a new method for the MDS testing of matrices over finite fields and shows its application to the (8 × 8)-matrices of a special form with many 1s and few different elements; these matrices were introduced by Junod and Vaudenay. For the proposed method we obtain some theoretical and experimental estimates of effectiveness. Moreover, the article comprises a list of some MDS matrices of the above-indicated type.

We study two generalizations of the classical problem of fast exponentiation, namely: Bellman’s problemon computational complexity (the minimal number ofmultiplications) based only on the variables of a normalized monomial of m variables and Knuth’s problem on the complexity of the simultaneous calculation of a system of m powers of one variable. Some results for these problems are reviewed in the paper. The asymptotic complexity bounds for Bellman’s and Knuth’s problems are improved for the cases whenmand complexity behave similarly (have the same growth order). The upper and lower complexity bounds for almost all sets of exponents for Bellman’s and Knuth’s problems that are established provide the complexity growth asymptotics for a wide range of relations between parameters (the number of variables or the computed exponents, the maximal power, and the product of all powers). Moreover, they guarantee the ratio of the upper and lower bounds not exceeding 5/3 for all relations between the parameters.

We describe the class of graphs whose each subgraph has the next property: The maximal number of disjoint 4-paths is equal to the minimal cardinality of sets of vertices such that every 4-path in the subgraph contains at least one of these vertices. We completely describe the set of minimal forbidden subgraphs for this class. Moreover, we present an alternative description of the class based on the operations of edge subdivision applied to bipartite multigraphs and the addition of so-called pendant subgraphs, isomorphic to triangles and stars.

Under consideration is the Successive Minima Problem for the 2-dimensional lattice with respect to the order given by some conic function f.We propose an algorithm with complexity of 3.32*log_2(R)+O(1) calls to the comparison oracle of f, where R is the radius of the circular searching area, while the best known lower oracle complexity bound is 3*log_2(R) + O(1).We give an efficient criterion for checking that given vectors of a 2-dimensional lattice are successive minima and form a basis for the lattice.Moreover, we show that the similar Successive Minima Problem for dimension n can be solved by an algorithm with at most (O(n))^{2n}*log_2(R) calls to the comparison oracle. The results of the article can be applied to searching successive minima with respect to arbitrary convex functions defined by the comparison oracle.

We consider the minimization problem for a symmetric quasiconvex function defined by an oracle on the set of integer points of a square. We formulate an optimality criterion for the solution, obtain a logarithmic lower bound for the complexity of the problem, and propose an algorithm for which the number of inquiries to the oracle is at most thrice the lower bound.

The complexity of realization of *k*-valued logic functions by circuits in a special infinite basis is under study. This basis consists of Post negation (i.e. function *x*+1(mod *k*)) and all monotone functions. The complexity of the circuit is the total number of elements of this circuit. For an arbitrary function *f*, we find the lower and upper bounds of complexity, which differ from one another at most by 1. The complexity has the form 3log_3 (*d*(*f*)+1)+*O*(1), here *d*(*f*) is the maximum number of the value decrease of the value of *f* taken over all increasing chains of tuples of variable values. We find the exact value of the corresponding Shannon function which characterizes the complexity of the most complex function of a given number of variables.

The 3-coloring problem for a given graph consists in verifying whether it is possible to divide the vertex set of the graph into three subsets of pairwise nonadjacent vertices. A complete complexity classification is known for this problem for the hereditary classes defined by triples of forbidden induced subgraphs, each on at most 5 vertices. In this article, the quadruples of forbidden induced subgraphs is under consideration, each on at most 5 vertices. For all but three corresponding hereditary classes, the computational status of the 3-coloring problem is determined. Considering two of the remaining three classes, we prove their polynomial equivalence and polynomial reducibility to the third class.

We describe the hereditary class of graphs, whose every subgraph has the property that the maximum number of disjoint 5-paths (paths on 5 vertices) is equal to the minimum size of the sets of vertices having nonempty intersection with the vertex set of each 5-path. We describe this class in terms of the "forbidden subgraphs" and give an alternative description, using some operations on pseudographs.

For each n and d, we describe the structure of trees with the maximal possible number of greatest independent sets in the class of n-vertex trees of vertex degree at most d. We show that for all even n an extremal tree is unique but uniqueness may fail for odd n; moreover, for d = 3 and every odd n>6, there are exactly ceil{(n-3)/4} + 1 extremal trees. In the paper, the problem of searching for extremal (n; d)-trees is also considered for 2-caterpillars, i.e., trees in which every vertex lies at distance at most two from some simple path. For each n and d=3,4, we completely reveal all extremal 2-caterpillars on n vertices each of which has degree at most d.

The independent set problem for a given simple graph consists in computing the size of a largest subset of its pairwise nonadjacent vertices. In this article, we prove the polynomial solvability of the problem for the subcubic planar graphs with no induced tree obtained by identifying the ends of three paths of lengths 3, 3, and 2 respectively.

We obtain some lower bounds for the complexity of word separation by occurrences of subwords. In the case of length 1 subwords, we show that the bound is exact up to a constant factor. Connection with the problem of separating words by automata is considered.