Cheap and Secure Web Hosting Provider : See Now

[Solved]: Implementing general vertex folding procedure in an undirected graph

, , No Comments
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):

Degree 2

which reduces to

Reduced 2


Degree 3

which reduces to

enter image description here.

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:

2-4-2 reduced

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: What you want is described in Proposition 2.6.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback