# Minimum Vertex Cover (MVC)#

Given an undirected graph with a set of nodes V and edges E, A vertex cover of a graph is a set of nodes that includes at least one endpoint of every edge of the graph. The Minimum Vertex Cover (MVC) problem is an optimisation problem that find smallest vertex cover of a given graph.

```import networkx as nx
import csv
import matplotlib.pyplot as plt

from mvc import qubo_mvc, qubo_mvc_penalty, mvc_feasibility, mvc_easy_fix, mvc_energy

""" Load graph from csv file
"""

with open(filename, 'r', newline='') as f:
data = [[int(row), int(row), float(row)] for row in reader]

nodes = [k0 for k0, k1, v in data if k0 == k1]
edges = [[k0, k1] for k0, k1, v in data if k0 != k1]

g = nx.Graph()

node_weights = {k0: {'weight': v} for k0, k1, v in data if k0 == k1}
edge_weights = {(k0, k1): {'weight': v} for k0, k1, v in data if k0 != k1}

nx.set_edge_attributes(g, edge_weights)
nx.set_node_attributes(g, node_weights)

return g
```

csv Format:

0,0,0.4696822179283675 1,1,0.6917392308135916 2,2,0.7130420958314817 3,3,0.49342677332980056 4,4,0.49661600571433673 5,5,0.55601135361347 6,6,0.2831095711244086 7,7,0.18737823232636885 0,1,0.98602725407379 1,2,0.935853268681996 2,3,0.23080434023289664 4,5,0.25521731195623476 5,6,0.37096743935296606 6,7,0.04408120693490547 0,2,0.5619060764177991 4,7,0.48402095290884917 1,6,0.7106584134580318

```g = load_csv('mvc.csv')
```
```pos = nx.spring_layout(g, seed=1234)
nx.draw(g, pos)
```
```print(f'Number of node is {len(g.nodes)}')
print(f'Number of edge is {len(g.edges)}')
```
```Number of node is 8
Number of edge is 9
```

## QUBO formulation#

### Estimate penalty#

```penalty = qubo_mvc_penalty(g)
print(f'The penalty is {penalty}')
```
```The penalty is 1.6548482220717595
```

### Formulate QUBO (weighted minimum vertex cover)#

```linear, quadratic = qubo_mvc(g, penalty=penalty)
print(f'Number of linear terms: {len(linear)}')
```
```Number of linear terms: 8
```

### Generate random solutions#

```import numpy as np
rng = np.random.default_rng(seed=1234)
random_solution = {i: rng.integers(2) for i in g.nodes}
print(f'The random solution is {random_solution}\n')
```
```The random solution is {0: 1, 1: 1, 2: 1, 3: 0, 4: 0, 5: 1, 6: 0, 7: 0}
```

### Check feasibility#

```feasibility = mvc_feasibility(g, random_solution)
print(f'The feasibility is {feasibility}\n')
```
```The feasibility is False
```

### Fix broken constraints#

```fixed_solution = mvc_easy_fix(g, random_solution)
print(f'After fixation, the solution is {fixed_solution}\n')
```
```After fixation, the solution is {0: 1, 1: 1, 2: 1, 3: 0, 4: 1, 5: 1, 6: 1, 7: 0}
```
```feasibility = mvc_feasibility(g, fixed_solution)
print(f'The feasibility is {feasibility}\n')
```
```The feasibility is True
```

### Visualisation#

```fig, (ax0, ax1) = plt.subplots(1, 2, figsize=(12.8,4.8))
colour_b4fix = ['C1' if random_solution[n] else 'C0' for n in g.nodes]
colour_fixed = ['C1' if fixed_solution[n] else 'C0' for n in g.nodes]
nx.draw(g, pos, node_color=colour_b4fix, ax=ax0)
ax0.set_title(f'Vertex cover in orange before fix')
nx.draw(g, pos, node_color=colour_fixed, ax=ax1)
ax1.set_title(f'Vertex cover in orange after fix')
```
```Text(0.5, 1.0, 'Vertex cover in orange after fix')
```

### Calculate energy#

```energy = mvc_energy(g, fixed_solution)
print(f'The energy is {energy}')
```
```The energy is 3.2102004750256556
```

## Hamiltonian of the MVC problem#

```ham = hamiltonian_mvc(g, penalty=penalty, dense=True)
```
```[Qibo 0.1.8|INFO|2022-11-01 10:26:19]: Using numpy backend on /CPU:0
```

## Solve the hamiltonian with QAOA#

```from qibo import models, hamiltonians

# Create QAOA model
qaoa = models.QAOA(ham)

# Optimize starting from a random guess for the variational parameters
initial_parameters = 0.01 * np.random.uniform(0,1,2)
best_energy, final_parameters, extra = qaoa.minimize(initial_parameters, method="BFGS")
```
```[Qibo 0.1.8|WARNING|2022-10-31 14:14:37]: Calculating the dense form of a symbolic Hamiltonian. This operation is memory inefficient.
```