Research of some intractable problems in the class of prefractal graphs with variable trajectory generation

Abstract

Intractable problems on graphs, such as enumeration, selection of subgraphs with given characteristics, become especially relevant on large graphs and networks. In this case, the variability and dynamism of network structures lead to an «additional» complication of the search for solutions to discrete optimization problems. To solve such problems, particular statements with restrictions are proposed, and sub-classes of graphs are distinguished for which solutions can be found under certain conditions. The paper proposes a class of prefractal graphs and investigates particular statements of NP-complete problems. The article studies NP-complete problems on prefractal graphs: isomorphism to a subgraph, degree constrained spanning tree, maximum leaf spanning tree, balanced complete bipartite subgraph, bipartite subgraph, planar subgraph. The conditions are identified under which for some subproblems it is possible to obtain an answer about existence and construct polynomial algorithms for finding solutions. As an example, algorithms for searching for spanning trees and packing bipartite graphs are proposed. The developed algorithms are polynomial and are based on well-known algorithms that are used in the form of procedures. In fact, the paper proposes to use the class of prefractal graphs as a tool for studying NP-complete problems and identifying conditions for their solvability. The development of polynomial algorithms for dynamic graphs will make it possible to solve with improved characteristics such well-known applied problems as the selection of subgraphs in large dynamic networks —the selection of communities in social networks; solution of multicriteria problems in large-scale transport and logistics systems; search and highlighting of ddos attacks in cryptocurrency systems and many other tasks.