1
$\begingroup$

By a "chain of k nodes", I mean k nodes lined up like a linked-list: o-o-o.....-o . By "do not contain a sub-chain of length >=3", I mean that no cover should contain two edges that shares a node. Lastly, we are interested in all such covers that meet this constraint, not just the optimal cover(s).

My current approach is as follows: Initialize two sets P = {1} and Q = {2} containing the first and second nodes respectively (labelled WLOG from left to right). Define N(P) and N(Q) to be the # of unique VC (satisfying sub chain constraint) that we can generate with P and Q. N(P) + N(Q) is what we want. Further, for any partial cover S ending with node i, N(S) = N(S U {i+2}) + N(S U {i+1, i+3}). I was curious if anyone knew what this count would analytically be in terms of k? Is it polynomial in k or exponential (or worse) in k?

$\endgroup$
  • $\begingroup$ (1) What do you mean by "unique"? (2) What does it mean that the cover "should not contain two edges that shares a node"? A vertex cover is a subset of the vertices, and not a subset of the edges. $\endgroup$ – Gamow May 25 '18 at 8:10
  • $\begingroup$ (1) I guess unique is redundant. Will correct that in the title. 2) Basically, any vertex cover with a sub-chain of length >=3, has at least one vertex that belongs to two edges. A sub-chain of length 3 is one that looks like this: o-o-o where all three nodes of this chain are in the cover. $\endgroup$ – Dabbler May 25 '18 at 8:32
  • $\begingroup$ Is this homework? The number of such vertex covers grows like $\Theta(1.324^k)$, and hence grows exponentially. $\endgroup$ – Gamow May 25 '18 at 9:12
  • $\begingroup$ This isn't homework. I'm doing independent research for fun and am trying to see if I can improve an approximation algorithm I've designed for a specific problem. $\endgroup$ – Dabbler May 25 '18 at 18:42

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.