# An Attention-Based Method for the Minimum Vertex Cover Problem on Complex Networks
## 3 Complement Information Based Attention Network
### Iterative Algorithm  
Finally, to grant that the output of the network is a minimal cover, we adapt the ConstructVC algorithm proposed in [40] to use the probability scores produced as outputs by our ACI-based model in place of nodes' degrees. In this way, we follow the suggestions of common successful heuristics in our DL-based methodology. Indeed, the ConstructVC algorithm is designed to build a minimal vertex cover given a graph iteratively. The modified version of the algorithm we propose is detailed in Algorithm 1 and consists of an extending phase and a shrinking phase. In the extending phase, we start with an empty set \(C\). The algorithm extends \(C\) by checking and covering an edge in each iteration: if the considered edge is uncovered, the endpoint with the higher computed probability score is added into \(C\). In the shrinking phase, we first calculate the loss values of vertices in \(C\) (where the loss is defined as the number of covered edges that would become uncovered by removing a vertex \(v\) from \(C\). ); then, we scan the \(C\) set and if a vertex \(v\in C\) has a loss value of 0, it is removed, and loss values of its neighbors are updated accordingly. Since the algorithm proposed follows the structure of the one proposed in [40] and only changes the probability according to which nodes are selected to be part of the final cover \(C\), it can be proved that the vertex set returned by the procedure is a minimal vertex cover. ```
Input: graph \(G=(N,E)\), probability score of each node Output: vertex cover of G \(C\leftarrow\emptyset\); for\(e\in E\)do if\(e\) is uncoveredthen  add the endpoint of \(e\) with higher probability score in \(C\)  end if  loss(v) \(\leftarrow\) for each \(v\in C\) for\(e\in E\)do ifonly one endpoint of \(e\) belongs to \(C\)then  for the endpoint \(v\in C,loss(v)++\)  end if  end for for\(v\in C\)do if\(loss(v)\) = 0 then \(C\gets C\setminus\{v\}\), update loss of vertices in \(N(v)\)  end if  end for
```  
**Algorithm 1**Build Vertex Cover  
```
Input: graph \(G=(N,E)\), probability score of each node Output: vertex cover of G \(C\leftarrow\emptyset\); for\(e\in E\)do if\(e\) is uncoveredthen  add the endpoint of \(e\) with higher probability score in \(C\)  end if  end for  end for
```  
**Algorithm 2**Build Vertex Cover  
```
Input: graph \(G=(N,E)\), probability score of each node Output: vertex cover of G \(C\leftarrow\emptyset\); for\(e\in E\)do if\(e\) is uncoveredthen  add the endpoint of \(e\) with higher probability score in \(C\



## 4 Experimental Evaluation

To train the neural model proposed, we create a synthetic dataset composed of randomly generated graphs. The final training dataset is composed of 3000 graphs for training and 600 graphs for validation with a random number of nodes between 5 and 2000. Half of the instances are relatively simple, with a random number of edges between the number of nodes itself and 1.5 times the number of nodes, i.e., low-density instances, and half more complex, with a random number of edges between 5 and 500 times the number of nodes, i.e., high-density instances. Given the number of nodes and the number of edges (iteratively extracted from a uniform distribution as described above), instances are built by choosing a graph uniformly at random from the set of all graphs with the given number of nodes and the given number of edges according to the method described in [50]. For each graph from the simple instances, we compute the cover using a branch-and-bound algorithm [51] to solve exactly the integer linear program formulated in Equation (1), setting as upper bound the initial number of nodes (updated each time to the size of the best solution found), as lower bound the dimension of the current vertex cover plus the dimension of the best vertex cover found for the subproblem considered and starting search from the node with highest degree in the subproblem considered.