### Article

## A method of graph reduction and its applications

The independent set problem for a given simple graph is to determine the size of a maximal set

of its pairwise non-adjacent vertices. We propose a new way of graph reduction leading to a new proof of

the NP-completeness of the independent set problem in the class of planar graphs and to the proof of NPcompleteness of this problem in the class of planar graphs having only triangular internal facets of maximal

vertex degree 18

This book constitutes the proceedings of the 13th International Computer Science Symposium in Russia, CSR 2018, held in Moscow, Russia, in May 2018.

The 24 full papers presented together with 7 invited lectures were carefully reviewed and selected from 42 submissions. The papers cover a wide range of topics such as algorithms and data structures; combinatorial optimization; constraint solving; computational complexity; cryptography; combinatorics in computer science; formal languages and automata; algorithms for concurrent and distributed systems; networks; and proof theory and applications of logic to computer science.

We study the computational complexity of finding a maximum independent set of vertices in a planar graph. In general, this problem is known to be NP-hard. However, under certain restrictions it becomes polynomial-time solvable. We identify a graph parameter to which the complexity of the problem is sensible and produce a number of both negative (intractable) and positive (solvable in polynomial time) results, generalizing several known facts.

We investigate regular realizability (RR) problems, which are the prob- lems of verifying whether intersection of a regular language – the input of the problem – and fixed language called filter is non-empty. In this pa- per we focus on the case of context-free filters. Algorithmic complexity of the RR problem is a very coarse measure of context-free languages com- plexity. This characteristic is compatible with rational dominance. We present examples of P-complete RR problems as well as examples of RR problems in the class NL. Also we discuss RR problems with context- free filters that might have intermediate complexity. Possible candidates are the languages with polynomially bounded rational indices.

The Independent Set Problem for planar graphs is known to be NP-complete. In this paper, its polynomial solvability for some subclasses of planar graphs is proved.

Market graph is known to be a useful tool for market network analysis. Cliques and independent sets of the market graph give an information about con- centrated dependent sets of stocks and distributed independent sets of stocks on the market. In the present paper the connections between market graph and classical Markowitz portfolio theory are studied. In particular, efﬁcient frontiers of cliques and independent sets of the market graph are compared with the efﬁcient frontier of the market. The main result is: efﬁcient frontier of the market can be well ap- proximated by the efﬁcient frontier of the maximum independent set of the market graph constructed on the sets of stocks with the highest Sharp ratio. This allows to reduce the number of stocks for portfolio optimization without the loss of quality of obtained portfolios. In addition it is shown that cliques of the market graphs are not suitable for portfolio optimization.

This book constitutes the refereed proceedings of the 23rd Annual Symposium on Combinatorial Pattern Matching, CPM 2012, held in Helsinki, Finalnd, in July 2012. The 33 revised full papers presented together with 2 invited talks were carefully reviewed and selected from 60 submissions. The papers address issues of searching and matching strings and more complicated patterns such as trees, regular expressions, graphs, point sets, and arrays. The goal is to derive non-trivial combinatorial properties of such structures and to exploit these properties in order to either achieve superior performance for the corresponding computational problems or pinpoint conditions under which searches cannot be performed efficiently. The meeting also deals with problems in computational biology, data compression and data mining, coding, information retrieval, natural language processing, and pattern recognition.

We study the following computational problem: for which values of k, the majority of n bits MAJn can be computed with a depth two formula whose each gate computes a majority function of at most k bits? The corresponding computational model is denoted by MAJk o MAJk. We observe that the minimum value of k for which there exists a MAJk o MAJk circuit that has high correlation with the majority of n bits is equal to Θ(n1/2). We then show that for a randomized MAJk o MAJk circuit computing the majority of n input bits with high probability for every input, the minimum value of k is equal to n2/3+o(1). We show a worst case lower bound: if a MAJk o MAJk circuit computes the majority of n bits correctly on all inputs, then k ≥ n13/19+o(1). This lower bound exceeds the optimal value for randomized circuits and thus is unreachable for pure randomized techniques. For depth 3 circuits we show that a circuit with k = O(n2/3) can compute MAJn correctly on all inputs.

This book constitutes the refereed proceedings of the 44th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2018, held in Krems, Austria, in January/February 2018. The 48 papers presented in this volume were carefully reviewed and selected from 97 submissions. They were organized in topical sections named: foundations of computer science; software engineering: advances methods, applications, and tools; data, information and knowledge engineering; network science and parameterized complexity; model-based software engineering; computational models and complexity; software quality assurance and transformation; graph structure and computation; business processes, protocols, and mobile networks; mobile robots and server systems; automata, complexity, completeness; recognition and generation; optimization, probabilistic analysis, and sorting; filters, configurations, and picture encoding; machine learning; text searching algorithms; and data model engineering.

We consider certain spaces of functions on the circle, which naturally appear in harmonic analysis, and superposition operators on these spaces. We study the following question: which functions have the property that each their superposition with a homeomorphism of the circle belongs to a given space? We also study the multidimensional case.

We consider the spaces of functions on the m-dimensional torus, whose Fourier transform is p -summable. We obtain estimates for the norms of the exponential functions deformed by a C1 -smooth phase. The results generalize to the multidimensional case the one-dimensional results obtained by the author earlier in “Quantitative estimates in the Beurling—Helson theorem”, Sbornik: Mathematics, 201:12 (2010), 1811 – 1836.

We consider the spaces of function on the circle whose Fourier transform is p-summable. We obtain estimates for the norms of exponential functions deformed by a C1 -smooth phase.

The problem of minimizing the root mean square deviation of a uniform string with clamped ends from an equilibrium position is investigated. It is assumed that the initial conditions are specified and the ends of the string are clamped. The Fourier method is used, which enables the control problem with a partial differential equation to be reduced to a control problem with a denumerable system of ordinary differential equations. For the optimal control problem in the l2 space obtained, it is proved that the optimal synthesis contains singular trajectories and chattering trajectories. For the initial problem of the optimal control of the vibrations of a string it is also proved that there is a unique solution for which the optimal control has a denumerable number of switchings in a finite time interval.

For a class of optimal control problems and Hamiltonian systems generated by these problems in the space *l *2, we prove the existence of extremals with a countable number of switchings on a finite time interval. The optimal synthesis that we construct in the space *l *2 forms a fiber bundle with piecewise smooth two-dimensional fibers consisting of extremals with a countable number of switchings over an infinite-dimensional basis of singular extremals.

This proceedings publication is a compilation of selected contributions from the “Third International Conference on the Dynamics of Information Systems” which took place at the University of Florida, Gainesville, February 16–18, 2011. The purpose of this conference was to bring together scientists and engineers from industry, government, and academia in order to exchange new discoveries and results in a broad range of topics relevant to the theory and practice of dynamics of information systems. Dynamics of Information Systems: Mathematical Foundation presents state-of-the art research and is intended for graduate students and researchers interested in some of the most recent discoveries in information theory and dynamical systems. Scientists in other disciplines may also benefit from the applications of new developments to their own area of study.

In this paper, we construct a new distribution corresponding to a real noble gas as well as the equation of state for it.