## 1 Introduction  
Today, complex cyber-physical systems (CPSs) depend highly on and suffer from deliberate hostile cyber-attacks. As the number of Internet users grows at an unprecedented rate, roughly doubling annually, the number of cybertimes steadily increases yearly [1, 2, 3]. There is a daily and ongoing need for risk management of existing CPSs, including vulnerability analysis of hardware and software assets constantly threatened by hostile attacks. Vulnerability analysis and the development of efficient algorithms aimed at estimating/mitigating the consequences of hostile attacks on cyber-physical systems are the most crucial research areas to ensure CPS's cybersecurity. These algorithms provide a rigorous, scientifically sound engineering approach to analyzing and preventing adversarial attacks. The development and analysis of one such algorithm is the subject of this research. Graphs are a powerful and widely used tool in all aspects of cyber-attack investigation. The first comprehensive analysis of an adversarial cyber-attack based on a graph model was performed in 1998 by [PERSON] and [PERSON] [4]. However, their approach required exponential computational time to generate the desired graph. Later, [PERSON] et al. [5] introduced a very productive concept of an exploit dependency, which allowed attack graphs to be generated much more efficiently. To investigate the vulnerability of the cyber network, researchers in [4] introduced and used a specific type of directed graph called an attack graph (AG) to describe and analyze malicious attacks and network insecurities visually. Analysis and research of attack graphs can help cyber-defense professionals identify vulnerabilities in a network that an attacker could exploit, thereby helping to strengthen the network's defenses. Typically, each node in an attack graph corresponds to a malicious event caused by attackers, and the edges correspond to the causal relationships between events. Such a graph represents a merged set of attack paths, each representing a sequence of steps an attacker can take to compromise the relevant network. A significant difference between attack graph analysis and other adversarial risk analysis methods is that AGs are constructed primarily from the attacker's point of view so that the defender can better understand the attacker's intentions and better organize the defense. Since different studies use different terms and various definitions related to cyber-attacks and related graph models, we provide the reader with the terms used in this paper in Table 1 in Appendix A. Given the extensive research conducted in the graph-based cybersecurity domain, this paper focuses on and references the most influential pioneering studies (see, for example, [6; 7; 8; 9; 10; 11], among many others). Interested readers are encouraged to consult the comprehensive surveys for a more detailed discussion of various problem formulations, models, and corresponding vulnerability analysis methods [12; 13; 14; 15; 16; 17]. In this paper, we focus on two relatively close attack graph formalisms that have been the most well-studied in the literature during the past decades for modeling computer networks from a cybersecurity perspective: exploit-dependency graphs (EDGs) [5; 6; 7; 8; 9; 10; 11] and AND/OR graphs (AOGs) [18; 19; 20; 21; 22; 23; 24; 25]. The widespread popularity of EDG and AOG attack models is due to their broad applicability, relatively moderate complexity, and scalability in graph generation. We next recall the corresponding definitions. The first popular formal model, called the exploit dependency graph, is a directed graph consisting of two types of nodes: exploit and condition nodes. Typically, an exploit node corresponds to a known vulnerability in the network under consideration; and a condition node represents a condition or prerequisite that must be fulfilled or achieved for a successful exploit. Edges represent logical or technological connections between nodes. Other interpretations of nodes and edges are widely known in the literature.