Set Cover and its Dual

For any given $($undirected$)$ graph G $=($V$,$E$),$ a subset S $$ V of nodes is

said to cover G if for each edge e $=\{$u$,$v$\}$ in E either u in S or v in S$.$ Note

that every graph G $=($V$,$E$)$ has a covering set, since in particular we could

take S $=$ V$.$

We are interested in finding a covering set which is as small as possible.

This problem is highly relevant in practice. For instance, a network of roads

can be modeled as a graph in which each intersection is assigned to a node

and every road corresponds to an edge. We can cover every road by placing

a monitor or guard only at nodes in a minimal covering set.

Formulate this problem as an integer LP$.$ Discuss how you could $$relax$$

this integer LP$,$ by loosening some constraints to obtain a genuine LP whose

solution could be used to construct a covering set. Then, write down the

dual of your LP