Covering k edges with minimum number of vertices

Question

I am trying to write a DP algorithm that calculates the minimum number of vertices we need to select in order to cover k edges on a graph.

The code I have written so far is:

#include<iostream>

#include<vector>

#include<list>

#include<set>
#include<algorithm> 
#include <tuple>

using namespace std;

int edges[10000][10000]={0}; //which edges I have covered
int adjacency[10000][10000]={0}; //the graph in an array
int K;
int sum=0;

int DP(int i,int j){
    if (j==K) return 1;
    int neys=0; //number of neighbors
    for (int m=0; m<10000; m++){ //scan the neighbor array
         if(adjacency[i][m]==1) {  //if I find a neighbor
            if(edges[i][m]==0) neys++; //if I have not taken this edge before into consideration
            edges[i][m]=1; //mark it as covered
         }
    }
    printf("i: %d\n",i);
    for (int m=0; m<10000; m++) //for all neighbors of i
        if(adjacency[i][m]==1) { //if m is a neighbor
            sum=min(1+DP(m,j+neys),DP(m,j)); //then take the minimum if I include it or not
            printf("sum: %d\n",sum);
        }
    return sum;
}

int main() {

    int N;
    int begin;
    scanf("%d %d",&N,&K);


    for (int i = 0; i < N - 1; i++) {

        int u,v;

        scanf("%d %d",&u,&v);
        if (i==0) begin=u;
        adjacency[u][v]=1;


    }

    int sol=DP(begin,0);
    printf("%d\n",sum);
}

This code is producing the wrong output for some reason. However, if it was right I suspect it would not be very fast(exponential complexity). Can you suggest an algorithm?

Example: for input: 9 6 1 2 1 3 1 4 2 5 2 6 3 7 4 8 4 9

The expected output is 2

My program outputs 0.

After seeing an answer below I came up with the following code:

#include <iostream>
#include <tuple>
#include <bits/stdc++.h>

using namespace std;

using MyKey = tuple<int, int, int, int>;

map<MyKey, int> glob;

int numEdges[100000];

tuple<int,int> compareAndGetBest(tuple<int,int> a, tuple<int,int> b){
 if (get<0>(a) == get<0>(b)){
    if (get<1>(a) >= get<1>(b)) return a;
    else return b;
 }
 else {
    if (get<0>(a) < get<0>(b)) return a;
    else return b;
 }
}

tuple<int,int> f(vector<vector<int>> map, int u, int i,int k,int childEdge){
  //printf("u: %d , i: %d k: %d childEdge: %d\n",u,i,k,childEdge);
  if (!glob[{u,k,i,childEdge}]==0) return make_tuple(glob[{u,k,i,childEdge}],k);


  tuple <int,int> result;

  if (k <= 0){
    result=make_tuple(0,0);
    glob[{u,k,i,childEdge}]=get<0>(result);
    return result;
  }


  if (i < 0){
    result=make_tuple(1000000,0);
    glob[{u,k,i,childEdge}]=get<0>(result);
    return result;
  }


  tuple <int,int> best = f(map, u, i-1, k, childEdge);



  int v = map[u][i];

  if (map[v].size()==0){  
    glob[{u,k,i,childEdge}]=get<0>(best);   
    return best;
  }


  int max = min(k, numEdges[v]);

  int l = map[v].size();


  for (int j=1; j<=max; j++){
    int max_j = (j - l);
    tuple <int,int> a   = f(map, v, l-1, max_j, 0);
    tuple <int,int> fa  = f(map, u, i-1, k-max_j-l-childEdge, childEdge);

    tuple <int,int> b  = f(map, v, l-1, j, 1);
    tuple <int,int> fb = f(map, u, i-1, k-j, childEdge);


    get<0>(a)  = get<0>(a) + 1;
    get<1>(a)  = get<1>(a) + l + childEdge;


    tuple <int,int> na = make_tuple(get<0>(a) + get<0>(fa), get<1>(a) + get<1>(fa));

    tuple <int,int> nb = make_tuple(get<0>(b) + get<0>(fb), get<1>(b) + get<1>(fb));

    best = compareAndGetBest(best, compareAndGetBest(na, nb));

  }

  glob[{u,k,i,childEdge}]=get<0>(best);
  return best;
}

int getNumEdges(vector<vector<int>> map,int u){
    int count=0;

    if (map[u].size()==0){
        return 0;
    }

    else {
        for (auto v: map[u]){
            if (map[v].size()>0){
                numEdges[v]=getNumEdges(map,v);
                count += 1 + numEdges[v];
            }
            else count +=1;
        }
    }

    numEdges[u]=count;

    return numEdges[u];

}

int main(int argc,char **argv){
    int N,K;
    FILE *fp;
    vector<vector<int> > myvec;
    fp=fopen(argv[1],"r");
    fscanf(fp,"%d %d",&N,&K);
    myvec.resize(N+1);
    for(int i=1 ; i<N ; i++){
        //printf("i: %d \n",i);
        int u, v;
        fscanf(fp,"%d %d",&u,&v);
        myvec[u].push_back(v);
    }

    int whatever=getNumEdges(myvec,1);
    //for (int k=1;k<=N-1;k++) printf("numEdges[%d]= %d \n",k,numEdges[k]);

    int l = myvec[1].size();

    tuple<int,int> a = f(myvec, 1, l-1, K, 1);
    tuple<int,int> b = f(myvec, 1, l-1, K-l, 0);

    tuple<int,int> ans=compareAndGetBest(a, make_tuple(get<0>(b)+1,get<1>(b)+l));
    printf("%d\n",get<0>(ans));
}

Answer 1

(This answer applies to trees, which seems to be what this question is about, given a strikingly similar one here and a closed one here.)

Here's a naive recursion in JavaScript (heavily commented) that uses a simple map of each parent vertex to its children, that's also decorated with the number of edges in the subtree. (The code could benefit from more example cases to refine with, or possibly rule the concept incorrect.)

The idea is to treat each child together with its parent, where if the parent is selected, the caller has already subtracted the edges to the children from k. Recursive calls go both back to an earlier child (with the same parent-assignment state), as well as trying different values of k from the current subtree, either selecting or skipping the child itself, a choice featured in the recursion.

The recurrence returns a tuple, (c, m), where c is the minimal cost (number of vertices) and m is the number of edges covered (which could be greater than k).

Each node has a search space of O(|edges in subtree|). Seems like O(|V| * k) might be possible?

// Returns a tuple, `(c, m)`, where `c` 
// is the cost (number of vertices) and `m`
// is the number of edges covered (which 
// could be greater than `k`).
// 'u' is the root of the tree/subtree,
// 'i' is the index of a child of 'u',
// 'childEdge' is 1 if the root is
// not used, matching the edge count
// we can add to each child chosen.
// If 'childEdge' is 0, it implies
// k was already adjusted by the caller.
function f(map, u, i, k, childEdge){
  // Base case
  if (k <= 0)
    return [0, 0]

  // Recursion limit
  if (i < 0)
    return [Infinity, 0]
  
  // Without the ith child
  let best = f(map, u, i-1, k, childEdge)
    
  // Current child
  let v = map[u].children[i]
  
  // Child has no subtree,
  // it's never optimal to use a leaf
  if (!map[v])
    return best
  
  /* Try different edge quantities from the subtree */
  
  let max = Math.min(k, map[v].numEdges)
  let l = map[v].children.length
  
  for (let j=1; j<=max; j++){
    // If we choose the child, subtract
    // its children's count but apply a 0
    // childEdge, as well as any childEdge
    // for the child-as-parent. numEdges includes
    // edges from the child-as-parent, subtract them.
    let max_j = (j - l) 
    let [ac, am] = f(map, v, l-1, max_j, 0)
    let [fac, fam] = f(map, u, i-1, k-max_j-l-childEdge, childEdge)
    
    let [bc, bm] = f(map, v, l-1, j, 1)
    let [fbc, fbm] = f(map, u, i-1, k-j, childEdge)
    // Add 'v' and the edges to its
    // children to the branch
    // where 'v' was used.
    ac = ac + 1
    am = am + l + childEdge

    let a = [ac + fac, am + fam]
    let b = [bc + fbc, bm + fbm]

    // Choose between a and b
    best = compareAndGetBest(
      best,
      compareAndGetBest(a, b)
    )
  }
  return best
}

// [c, m] are [cost, num_edges_covered]
// Return larger m if possible
function compareAndGetBest(a, b){
  if (a[0] == b[0]){
    return a[1] >= b[1] ? a : b
  } else {
    return a[0] < b[0] ? a : b
  }
}

function getNumEdges(map, u){
  if (!map[u]){
    return 0
    
  } else {
    let count = 0
    for (let v of map[u].children){
      if (map[v]){
        map[v]["numEdges"] = getNumEdges(map, v)
        count += 1 + map[v]["numEdges"]
      } else {
        count += 1
      }
    }
    return map[u]["numEdges"] = count
  }
}

function getChildrenMap(edges){
  return edges.reduce(function(acc, [u, v]){
    if (acc[u])
      acc[u].children.push(v)
    else
      acc[u] = {children: [v]}
    return acc
  }, {})
}

function partialVertexCover(edges, k){
  var childrenMap = getChildrenMap(edges)
  getNumEdges(childrenMap, 1)
  var l = childrenMap[1].children.length

  console.log(JSON.stringify(childrenMap) + "\n")
  
  let a = f(childrenMap, 1, l-1, k, 1)
  let [bc, bm] = f(childrenMap, 1, l-1, k-l, 0)

  return compareAndGetBest(a, [bc + 1, bm + l])
}

function main(){
  var edges = [
    [1, 2],
    [1, 3], //        1
    [1, 4], //     /  |  \
    [2, 5], //    2   3   4
    [2, 6], //   / \  |  / \
    [3, 7], //  5   6 7 8   9
    [4, 8],
    [4, 9]
  ]

  var k = 6

  console.log(partialVertexCover(edges, k) + "\n")

  edges = [
    [1, 2],
    [1, 3], //       1
    [1, 4], //    /  |  \
    [2, 5], //   2   3   4
    [3, 6], //   |   |   |
    [4, 7]  //   5   6   7
  ]

  console.log(partialVertexCover(edges, k) + "")
}

main()