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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.