Understanding graph layering approximation algorithms

Question

I've been trying to understand the Graph Layering Approximation Algorithms for both Set Cover and Feedback Vertex Set problems. I am using Vijay V. Vazirani's "Approximation Algorithms" book. So let me show you my train of thougts based on pages 17-18 from this book.

The weight function for nodes, based on their degrees is used: $w(v) = c * deg(v)$ where:

c - constant, such that c>0
v - vertex of a graph
deg(v) - degree of a vertex v

So now we take a graph, compute $c = min{(w(v) / deg(v))}$ for all vertices, then we compute $t(v) = c * deg(v)$, and for all vertices define $w'(v) = w(v) - t(v)$

We remove all vertices for which $w'(v) == 0$ and we repeat until all vertices have weight of 0.

Now for my problem: If I assign $c = 1$, then function $w(v)$ for each vertex:

$w(v) = 1 * deg(v) = deg(v)$.
$min{(w(v) / deg(v))} = min{(deg(v)/deg(v))} = 1$.
$t(v) = deg(v)$
$w'(v) = deg(v) - deg(v) = 0$.

So for all vertices in step one I have weights 0 ALWAYS. Am I missing something? Should $c$ vary for each vertex? If so, how should I assign $c$ to vertices? Is there some range of integers? Example of using this algorithm on a small graph would be nice, because I am not very good at reading Math notation

Answer 1

You use the wrong definition for $t(v)$. Instead of $c*deg(v)$ it is defined as $c*\delta(v)$ the decrease in cyclomatic number after removing $v$.

Answer 2

You should search "local ratio for approximation algorithms". This is the popular name of the layering algorithm in Vazirani's book. Bar-Yehuda has many papers on it. Below is the link to one of them: https://www.sciencedirect.com/science/article/abs/pii/S0304020808731013

Answer 3

First of all, the value of $c$ is calculating in each iteration using this formula: $$c=\min\left( \frac{w(v)}{\deg(v)} \right),$$ and there is no constant $c$ for assigning weight to all vertices.

Second, $c$ is a real parameter, not an integer.

Third, I think, in Vijay V. Vazirani's "Approximation Algorithms" book, page 19, first equation is wrong and had to define as follow: $$ w(v)\le\sum_{i\le j}t_i(v) $$ or

$$ w(v)=t_j(v). $$

Because $v \in W_j$ and in $j^{th}$ iteration $w'_j(v)=w(v)-t_j(v)=0\Rightarrow w(v)=t_j(v)$.