6
$\begingroup$

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

or

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:

2-4-2

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ After giving it a little thought, N(I) cannot be an intersection of neighborhoods of all vertices in I - this would be against the supposition related to the size of N(I), given the second or third example. Back to square one then... $\endgroup$ – helluin Sep 17 '14 at 14:19
1
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Wow! Thanks a lot. This is actually the third version of the paper that I see... Why would they do such a thing? $\endgroup$ – helluin Sep 18 '14 at 6:24
  • $\begingroup$ That's the unfortunate conference culture. Conference papers have a maximum page length, so all the details cannot be included, and often have never been completely determined by the authors. Often papers are wrong for this reason. Fortunately in this case the authors bothered to prepare a full version, and all the details work out. $\endgroup$ – Yuval Filmus Sep 18 '14 at 12:40
  • $\begingroup$ This is indeed very sad, since the last place I would expect such practices is academia... Well, thanks again! :) $\endgroup$ – helluin Sep 18 '14 at 15:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.