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?