# An Attention-Based Method for the Minimum Vertex Cover Problem on Complex Networks
## 2 Basic Concepts and Problem Definition  
In this section, we first introduce basic concepts about graphs and the MVC problem; then, we introduce the basics of the DL techniques adopted in this research. **Definition 1** (Graph). : _A Graph is a pair \(G=(N,E)\), where \(N\) is the set of nodes and \(E\) is the set of edges, such that each element of \(E\) is a pair of element of \(N\)._  
An edge that links two nodes \(u\in N\) and \(v\in N\) can be denoted as \((u,v)\in E\). Moreover, if \(E\) is not a symmetric relation, the graph is said to be _undirected_, and if edges are not weighted, the graph is said to be _unweighted_. Since we focus on these kinds of graphs, in the following, we will generally refer to graphs as unweighted, undirected graphs. At the node level, graphs can be represented by features that describe structural graph information. _Node degree_, i.e., the quantity of direct neighbors of a node (or the number of incident edges), is one of the most commonly used since it can naturally indicate the importance of a node within the graph. As for node-level description, graph-level features can be used. Among the most commonly used, _density_ conceptually provides an idea of how much connected a graph is and is measured by the ratio between edges and nodes within a graph, \(D=\frac{|E|}{|N|}\). Another relevant concept is _clique_, i.e., a set of vertices, all pairs of which are adjacent. **Definition 2** (Minimum Vertex Cover). : _Given an unweighted undirected graph \(G=(N,E)\), a vertex cover \(N^{\prime}\) is a subset of \(N:(u,v)\in E\Rightarrow u\in N^{\prime}\lor v\in N^{\prime}\). A minimum vertex cover is a vertex cover of the smallest possible size._  
This problem can be formulated as the following integer linear program:  
\[ \begin{array}{ll}\text{minimize}&\sum_{v\in N}x_{v}\\ \text{subject to}&x_{u}+x_{v}\geq 1&\forall(u,v)\in E\\ &x_{v}\in\{0,1\}&\forall v\in N\end{array}  \tag{1}\]  
where the objective function consists of minimizing the number of nodes belonging to the covering set, such that every edge of the graph is covered (\(x_{u}+x_{v}\geq 1\,\forall(u,v)\in E\)) and every vertex is either in the vertex cover or not (\(x_{v}\in\{0,1\}\)). With the above definitions we can state our objective as follows: Given an unweighted undirected graph \(G=(N,E)\), with \(N\) nodes and \(E\) edges and a minimum vertex cover \(N^{\prime}\) of \(G\), we want to find a parametric function which is able to map the input graph \(G\) to the set of covering nodes \(N^{\prime}\), \(f(G;\theta)=N^{\prime}\). The MVC problem does not have a unique optimal solution. The solution, i.e., the minimum covering set, mainly depends on the order according to which edges or nodes are scanned to determine whether they should be part of it. As an example, a very simple approximated approach to solving the problem consists of starting from the set \(E\) of all edges, where edges are arbitrarily ordered (suppose, without loss of generality, that they are named with capital letters, and they are ordered lexicographically). The approach consists of iteratively scanning this set so that at each iteration, edge \((u,v)\) is picked, and nodes \(u\) and \(v\) are added to the final covering set \(N^{\prime}\). Then, all the other edges in \(E\), which are either incident to \(u\) or \(v\) are removed. This is carried out until \(E\) is empty. \(N^{\prime}\) represents the final solution. Figure 1 shows an example of this. By applying the described approach to the left-side graph, assuming that edges are ordered lexicographically since edge \(A=(1,4)\) is the first scanned, the results would be \(N^{\prime}=(1,4)\). By changing the name of the edges (right-side graph) and applying the same procedure using the lexicographical order, the first scanned edge would be \(A^{\prime}=(1,3)\). Thus, the final result would be \(N^{\prime}=(1,3)\). Figure 1: Example of distinct optimal solutions for the same graph. Covering nodes are colored blue.