# min vertex cover to access k edges in a tree

I need to find the minimum number out of $$N$$ vertices on a tree with $$N-1$$ edges, so that at least $$K$$ edges of that tree are connected to these vertices.

For example, if $$N=9$$ and $$K=6$$ and we have this tree:

   Edges  |  Vertice #1  | Vertice #2
1            1          2
2            1          3
3            1          4
4            2          5
5            2          6
6            3          7
7            4          8
8            4          9


The right answer should be $$\mathrm{min}=2$$.

Any thoughts?

• – D.W. Jan 2 '20 at 19:22
• Did you try dynamic programming? – Neal Young Jan 3 '20 at 17:38
• @NealYoung I don't know about the OP, but I tried and had some problems finding the recursive function, could you help? – user102382 Jan 3 '20 at 17:57
• It's doable but tricky. Start by studying the DP algorithms for Vertex Cover in trees here: http://courses.csail.mit.edu/6.006/spring11/lectures/lec21.pdf. Maybe to get started assume that each node in the tree has degree at most 3. – Neal Young Jan 3 '20 at 18:30
• @Antti Röyskö Please give a look at this, I was told this can be solved by using Lagrange multipliers which is similar to another question I saw you answer – user102382 Jan 4 '20 at 23:52

There is a $$\mathcal{O}(nk)$$ DP approach.

Call an edge covered if we select a vertex next to it. Root the tree at an arbitrary vertex $$r$$. Define $$DP[i][b][t]$$ as the maximum number of edges in the subtree of node $$i$$ that can be covered by selecting at most $$t$$ nodes from the subtree. If $$b = 0$$ we are not allowed to select node $$i$$, and if $$b = 1$$ we must select it.

If we calculate this DP, we can solve the problem, as the minimum number of nodes to cover $$k$$ edges is the smallest $$t$$ for which $$max(DP[r][0][t], DP[r][1][t]) \geq k$$. Further note that it suffices to only calculate the $$DP$$ for $$t \leq k$$, as any $$k < n$$ nodes cover at least $$k$$ edges.

To give the recurrence to calculate the DP, we first give the knapsack-function: let $$K(V_{1}, \dots, V_{m})$$ be an array such that

$$\begin{equation*} K(V_{1}, \dots, V_{m})[t] = \max_{t_{1} + \dots + t_{m} = t} \sum_{j = 1}^{m} V_{j}[t_{j}] \end{equation*}$$

Note that $$K(K(V_{1}, \dots, V_{m-1}), V_{m}) = K(V_{1}, \dots, V_{m})$$, and that $$K(A, B)$$ can be directly calculated by the above formula in $$\mathcal{O}(|A| \cdot |B|)$$ time. Hence calculating $$K(V_{1}, \dots, V_{m})$$ takes $$\mathcal{O}(\sum_{i = 2}^{m} |V_{i}| \sum_{j = 1}^{i-1} |V_{j}|)$$ time regardless of the order we combine the sets in. If we are interested in only the first $$k$$ values of the DP, the complexity drops to $$\mathcal{O}(\sum_{i = 2}^{m} |V_{i}| \min(k, \sum_{j = 1}^{i-1} |V_{j}|))$$

Let $$C_{i}$$ be the set of children of node $$i$$, and $$C_{ij}$$ be the $$j$$th child of $$i$$. Then $$\begin{gather*} DP[i][0][t] = K(V_{1}, \dots, V_{|C_{i}|})[t]\\ DP[i][1][t] = |C_{i}| + K(V'_{1}, \dots, V'_{|C_{i}|})[t-1] \end{gather*}$$ Where $$\begin{gather*} V_{j}[t] = \max(DP[C_{ij}][0][t], DP[C_{ij}][1][t] + 1)\\ V'_{j}[t] = \max(DP[C_{ij}][0][t], DP[C_{ij}][1][t])\\ \end{gather*}$$ Calculating the answer with this recursion takes $$\mathcal{O}(nk)$$ time. Informally this is because over the course of the algorithm, we combine single-element DPs into a DP representing the whole tree. We do at most $$\frac{n}{k}$$ combinations of sets of size $$k$$, and any element costs us at most $$2k$$ time (if element $$x \in A$$ costs us $$|B|$$ time when calculating $$K(A, B)$$) before it gets merged into a set of size $$k$$, so the total amount of work is at most $$\mathcal{O}(k^{2} \frac{n}{k} + k n) = \mathcal{O}(nk)$$. This is easy but tedious to formalise with induction.

#include <iostream>
#include <vector>
#include <tuple>
using namespace std;
const int INF = (int)1e9 + 7;

vector<int> knapsack(const vector<int> a, const vector<int> b, int k) {
int n = a.size();
int m = b.size();
vector<int> c(n+m-1, -INF);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) c[i+j] = max(c[i+j], a[i] + b[j]);
}
if (c.size() > k) c.resize(k);
return c;
}

pair<vector<int>, vector<int>> dfs(int i, int p, int k, const vector<vector<int>>& g) {
vector<int> dp0 = {0, 0};
vector<int> dp1 = {-INF, (int)g[i].size() - (p != -1)};
for (auto t : g[i]) {
if (t == p) continue;
vector<int> dp0_t, dp1_t;
tie(dp0_t, dp1_t) = dfs(t, i, k, g);
int m = dp0_t.size();

vector<int> off0(m), off1(m);
for (int j = 0; j < m; ++j) off0[j] = max(dp0_t[j], dp1_t[j] + 1);
for (int j = 0; j < m; ++j) off1[j] = max(dp0_t[j], dp1_t[j]);
dp0 = knapsack(dp0, off0, k+1);
dp1 = knapsack(dp1, off1, k+1);
}
return {dp0, dp1};
}

int minCover(int k, const vector<vector<int>>& g) {
vector<int> dp0, dp1;
tie(dp0, dp1) = dfs(0, -1, k, g);
for (int i = 0;; ++i) {
if (max(dp0[i], dp1[i]) >= k) return i;
}
}

int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);

int n, k;
cin >> n >> k;

vector<vector<int>> g(n);
for (int i = 0; i < n-1; ++i) {
int a, b;
cin >> a >> b;
--a; --b;
g[a].push_back(b);
g[b].push_back(a);
}

int t = minCover(k, g);
cout << t << '\n';
}

• Thank you for this very nice solution. – shgr1092 Jan 8 '20 at 16:16
• Would this question interest you? I have been curious about an efficient answer for a while as no one has posted one. (There's also a link in the comments there to the online judge. It's in Latvian but Google translate worked for me :) – גלעד ברקן Jan 10 '20 at 13:39

A simple solution is to use the state $$dp(n,2,n)$$. Let $$dp(i,0,j)$$ be the maximum number of edges we can get by using $$\leq j$$ nodes in the subtree rooted at node $$i$$, with node $$i$$ itself not being in the vertex cover. Let $$dp(i,1,j)$$ be the same, except node $$i$$ is included in the vertex cover.

The transition itself is not obvious, but it can be done using a Knapsack-like method. Consider all the children of node $$i$$. Use all the values of $$dp(ch,0,c)$$ and $$dp(ch,1,c)$$ as items in two separate Knapsacks: one to calculate the full array $$dp(i,0)$$ and one to calculate the full array $$dp(i,1)$$. The costs of items are uniformly $$c$$, while the values are the following:

If calculating $$dp(i,0)$$: value of $$dp(ch,0,c)$$ is $$dp(ch,0,c)$$; value of $$dp(ch,1,c)$$ is $$dp(ch,1,c)+1$$.
If calculating $$dp(i,1)$$: value of $$dp(ch,0,c)$$ is $$dp(ch,0,c)+1$$; value of $$dp(ch,1,c)$$ is $$dp(ch,1,c)+1$$.

We can get the full arrays $$dp(i,0)$$ and $$dp(i,1)$$ directly from the end values of the Knapsacks (that is, the values of $$kn(last,j)$$ for all $$j$$). The Knapsack has $$O(\#children * n)$$ items per node, and runs in $$O(\#children * n * n)$$ per node. Therefore, the total complexity of the solution is $$O(n^3)$$. Please note that you will have to slightly modify the traditional 0-1 Knapsack to prevent two items which represent the same node from being taken; this is not very difficult. Also, when calculating the $$dp(i,1)$$ array, please note that the node $$i$$ itself is an extra node on the vertex cover.

I am note sure if there are solutions running in time faster than this one, but I would not doubt it.

• I will try to write this in c++. If I succeed I will add it to your answer. Thank you for taking the time to write this – user102382 Jan 6 '20 at 15:04
• I've been trying for the past few hours to write a code, but I can't figure out how to incorporate the knapsack problem in a dp function of my own – user102382 Jan 6 '20 at 19:41
• @maverick98 If I have time I'll write one some time. But, the easiest way is probably to use DFS to go through tree nodes, and at every node in the DFS, create a Knapsack problem and run a Knapsack. – shgr1092 Jan 7 '20 at 2:39