**Problem Detail:**

I'm implementing the algorithm presented in *"Improved Parameterized Upper Bounds for Vertex Cover"* paper (PDF). I'm a bit stumped by the `General-Fold`

procedure. What it should do is reduce the number of vertices (and) edges in the graph by finding specific structures (almost-crowns) and replacing them with a single vertex. (There is also a separate case, but I'm focusing on the described one now).

It goes like this:

Let $I$ be an independent set in $G$ (the graph) and let $N(I)$ be the neighbors of I. Suppose that $|N(I)|=|I|+1$ and for every $\emptyset\neq S \subset I$ we have $|N(S)|\geq{S}+1$.

1) If the graph induced by $N(I)$ is not an independent set, then there exists a minimum vertex cover in $G$ that includes $N(I)$ and excludes $I$).

(This is a 'standard' crown case - I have it implemented already with a separate approach.)2) If the graph induced by $N(I)$ is an independent set, let $G\prime$ be the graph obtained from $G$ by removing $I\cup N()$ and adding a vertex $u_I$ and then connecting $u_I$ to every vertex $v \in G\prime$ such that v was a neighbor of a vertex $u \in N(I)$ in $G$.

My problem is **how to find a structure** that would fulfill the suppositions about size as well as having an independent neighborhood? It's all roses when every vertex in $I$ is of the same degree, e.g. ($I$ is yellow, $N(I)$ is green):

which reduces to

or

which reduces to

.

If only that was the case - I'd just check the vertices of a specific degree, descending.

But unfortunately this reduction may apply to a set of vertices of differing degrees. An example:

note the different edges between yellow and green. It also reduces to:

What baffles me is what would the algorithm for that be, since **the paper states** that given a maximum size $k$ of a vertex cover existing in the graph, **it is possible to be done in $O(k^{2}\sqrt{k})$**.

Can anybody offer any help or advice or intuition on this?

EDIT: I think I might be understanding neighborhood incorrectly here - if we suppose that $N(I)$ contains the **intersection** of neighborhoods of every vertex in $I$, this would come down to the first two examples - where every vertex in $I$ is of the same degree...

Any thoughts?

###### Asked By : helluin

#### Answered By : Yuval Filmus

Take a look at the full version of the paper: http://www.sciencedirect.com/science/article/pii/S0304397510003609. What you want is described in Proposition 2.6.

###### Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/30060

**3.2K people like this**

## 0 comments:

## Post a Comment

Let us know your responses and feedback