title: Dynamic Programming: Vertex Cover of simple graphs
body: <p>I am looking to find an efficient algorithm to find the min-cost vertex cover of two specific graphs where vertices have varying cost. </p>
  
  <p>The first graph is a linked list of sorts, in which we have V={1...n} and E={{1,2},{2,3},{3,4}...{n-1,n}}</p>
  
  <p>The second graph is a simple cycle. Basically the same as above but with {n,1} being an edge as well.</p>
  
  <p>I have figured out a way to do the first one recursively, by simply exhaustively checking whether each node should be in the vertex cover or not. </p>
  
  <pre><code>VC(Graph G(V,E)):
    if(|V|=0) return 0
    u=first node of V
    v=second node of V
    return min(VC(Graph.remove(u)+cost(u),   //Case where the first node is in VC
               VC(Graph.remove(v,u))+cost(v)) //Case where second node is in VC
  </code></pre>
  
  <p>Yet this is truly inefficient, is there a way to improve on this using dynamic programming?</p>