<p>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). </p>

<p>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? </p>

CC BY-SA 4.0
2018-05-25T08:10:58.643Z
(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.
Gamow
CC BY-SA 4.0
2018-05-25T08:32:03.697Z
(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.
Dabbler
CC BY-SA 4.0
2018-05-25T09:12:56.337Z
Is this homework? The number of such vertex covers grows like $\Theta(1.324^k)$, and hence grows exponentially.
Gamow
CC BY-SA 4.0
2018-05-25T18:42:18.920Z
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.
Dabbler
<graph-theory><co.combinatorics><counting-complexity>
Counting vertex covers on a chain of k nodes that do not contain a sub-chain of length >=3
Dabbler
# Counting vertex covers on a chain of k nodes that do not contain a sub-chain of length >=3

(Asked by: username_0 on 2018-05-25)

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?

**Tags:** graph-theory, co.combinatorics, counting-complexity
> **Comments:**
> **username_1**: (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.  
> **username_0**: (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.  
> **username_1**: Is this homework? The number of such vertex covers grows like $\Theta(1.324^k)$, and hence grows exponentially.  
> **username_0**: 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.  

---

## 0 answers

