This question is concerned with the weighted vertex cover $($WVC$)$ problem discussed in class, and

also with the weighted set cover $($WSC$)$ problem defined below.

A WVC instance is a pair $(G,w)$ where $G=(V,E)$ is an undirected graph and $w$ is a function

that maps each vertex $v$ in $V$ to a positive integer weight $w(v).$ The goal is to find a minimum$-$

weight vertex cover of $G.($Recall that a vertex cover of a graph $G=(V,E)$ is a subset $U$ of $V$

such that $\{u,v\}U\frac{O}{?}$ for all edges $(u,v)$ in $E.$ The weight of a vertex cover $U$ is defined as

$\{$:${\displaystyle \underset{\text{v}\text{i}\text{n}\text{U}}{\overset{?}{}}}w(v).)$

A WSC instance I is a triple $(S,F,w)$ where $S$ is a finite set, $F$ is a collection of subsets of $S$

such that ${?}_{\text{T}\text{i}\text{n}\text{F}}T=S,$ and $w$ is a function that maps each set in $F$ to a nonnegative weight. Given

a WSC instance I, a subset $F^{\text{'}}$ of $F$ is said to be a set cover for I if ${?}_{Tin{F}^{\text{'}}}T=S,$ and the weight

of a set cover $F^{\text{'}}$ is defined as ${\displaystyle \underset{Tin{F}^{\text{'}}}{\overset{?}{}}}w(T).$ The goal is to find a minimum$-$weight set cover for I.

We define the "degree" of a WSC instance $(S,F,w)$ as the maximum, over all $x$ in $S,$ of

$|\{TinF|xinT\}|($i$.$e$.,$ the number of sets in $F$ that contain $x).$

$($a$)$ Show how to express a given WSC instance $I_1=(S,F,w)$ as a $0-1$ integer linear

program $($ILP$)I_2.$ Hint: Instance $I_2$ should have one variable for each set in $F.$

$($b$)$ Describe the LP relaxation $I_3$ of the $0-1$ ILP $I_2$ from part $($a$).$

$($c$)$ Explain how a WVC instance $I=(G,w)$ corresponds to a degree$-2$ WSC instance $I^{\text{'}}.$

$($d$)$ Recall that in class we presented a $2-$approximate polynomial$-$time WVC algo$-$

rithm based on LP rounding. Here we use LP rounding to develop a similar polynomial$-$time

approximation algorithm for WSC$.$ Let $k$ denote the degree of WSC instance $I_1.$ Explain

how to round an optimal fractional solution to LP $I_3$ of part $($b$)$ to obtain a $k-$approximate

solution to $0-1$ ILP $I_2.$ Be sure to address $(1)$ how the rounding is done, $(2)$ why the rounded

solution is feasible for $I_2,$ and $(3)$ why the rounded solution is within a factor of $k$ of optimal

for $I_2.$

Hint: You will need to use a "non$-$standard" rounding scheme, i$.$e$.,$ you will not want to

simply round each fractional value to the nearest integer.