0
$\begingroup$

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?

$\endgroup$
7
4
$\begingroup$

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';
}
$\endgroup$
2
  • $\begingroup$ Thank you for this very nice solution. $\endgroup$ – shgr1092 Jan 8 '20 at 16:16
  • $\begingroup$ 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 :) $\endgroup$ – גלעד ברקן Jan 10 '20 at 13:39
0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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 $\endgroup$ – user102382 Jan 6 '20 at 15:04
  • 1
    $\begingroup$ 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 $\endgroup$ – user102382 Jan 6 '20 at 19:41
  • 1
    $\begingroup$ @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. $\endgroup$ – shgr1092 Jan 7 '20 at 2:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.