# maximal independent set on grid-based graph proof of approximation ratio

We have a G = (V, E, w), in form of a grid graph with a single diagonal line in each grid in form of below. Where w is the V weight.

We use a greedy algorithm that takes in each step maximum weighted vertex and adds it to the set and removes all the adjacent vertices to the vertex. I want to prove that algorithm is 6-approximation.

Let $$W^*$$ be optimal solution $$O$$, and $$W$$ be greedy solution $$S$$. We build a mapping for each $$u \in O$$ and we define $$u'=u$$ if $$u\in S$$ else $$u'=$$ $$"u$$ neighbor" in $$S$$, that means at some iteration in greedy algorithm the $$u$$ was excluded and the $$u$$ neighbour $$w(u) \leqslant w(u')$$ was chosen.

$$W^* = \displaystyle\sum_{u \in O} w(u) \leqslant \displaystyle\sum_{u' \in S} w(u')$$.

Afterwards I'm bit confused how to prove that it's 6-approximation, as in each step when we select vertex from S, we remove only at most 3 vertices from O, based on the graph. I understand that it's 1/6 because of the number of neighbours of vertex, but I'm bit confused about that choosing non-optimal vertex can remove up to 3 vertices only.

• Let $u$ be the max-weight vertex. You can either select $u$ or not select $u$. If you select $u$, then you gain $w(u)$. If you don't select $u$, then what's the maximum possible gain you can get? In the best case, you can select all its neighbors, and gain $\sum_{v \in N(u)} w(v) \le \sum_{v \in N(u)} w(u) \le 6 w(u)$. Then you should note that the remaining graph in the first case is $G \setminus N'(u)$ (where $N'(u) = N(u) \cup \{u\}$), and in the second case - $G \setminus \cup_{v \in N(u)} N'(v)$, so the first graph includes the second one. The rest should be simple. – user114966 May 7 at 18:59