-

---
title: Assignment 6
author:
- Arjen Rouvoet
---

## 1: Weighted Max-SAT

It's trivial to perform this parallel to the proof in the book.
Let $Z_i$ be a random variable indicating whether clause $i$ is satisfied ($Z_i$ is $1$ if $i$ is
satisfied).
The expected contribution $W_i$ of the $i$'th clause with weight $w_i$ to the summed weight is:

(@) $E[W_i] = E[w_i Z] = w_i E[Z] = \frac{w_i}{2}$

This expectation is independent for all clauses, such that summing over all $m$ clauses:

(@) $E[S] = \sum_{i=1}^{m} E[W_i] = \sum_{i=1}^{m} \frac{w_i}{2} = \frac{\sum_{i=1}^{m} w_i}{2}$

$\blacksquare$


## 2: Max-Cut as Max-2-SAT

Given an instance $G = (V, E)$ of Max-Cut, we find an instance $S$ of Max-2-SAT as follows:

+ For each $(u, v) \in E$ add two clauses: $(u \vee v) \wedge (\neg u \vee \neg v)$ to $S$

We find that each set of such clauses is maximized for $(u \wedge \neg v) \vee (\neg u \wedge v)$
and that this means that the edge $(u, v)$ is in de cut.
If either of the two clauses is not satisfied, this means that the edge is not in de cut.

If $S$ has maximum $n$ out of $m$ clauses satisfied, then this means that the corresponding instance
of Max-Cut has maximum:

(@) $\lfloor \frac{n-(m-n)}{2} \rfloor = \lfloor \frac{2n-m}{2} \rfloor$

Having an $\alpha$-approximation for Max-2-Sat does not mean we have an $\alpha$ approximation for
Max-Cut.
This can be seen if one recognizes that in a Max-2-Sat instance derived from Max-Cut, always half of
the clauses can be satisfied, even if the cut is chosen as containing zero edges!

## 3:

## 4: Independent Set

a.  Given $n$ vertices and the fact that each vertice has a probability to survive of $1/d$, this
    gives the expected number of vertices that survive:

    (@) $E[S] = \frac{n}{d}$

    An edge only survives if both endpoints survive, starting with $\frac{nd}{2}$ edges:

    (@) $E[R] = \frac{nd}{2} \cdot \frac{1}{d^2} = \frac{n}{2d}$

b.  If we now remove all edges that remain by removing on of it's endpoints, we have an independent
    set of at least $\frac{n}{2d}$ nodes.

    Using the probabilistic method, we now know that at least one such independent set must exist
    for every such graph. $\blacksquare$